백준 4196 도미노

문제 URL : https://www.acmicpc.net/problem/4196

4196번: 도미노

 

 

문제 접근법 : 

ssc + 위상정렬을 이용한 문제입니다.

도미노를 최소한으로 건드려서 다 쓰러뜨리고 싶은데 어떻게 쓰러뜨려야할지 물어보는 문제입니다.

 

해당 그림이 

1->2

2->3

3->2 이럴경우 1번만 건드려서 2,3번을 전부 쓰러트려야하는데 ssc를 어떻게 해결하면 좋을지 생각해야합니다.

 

ssc로 그룹화 시켜주고 해당 그룹에서 다른그룹으로 가는 indegree가 없다면 

그것은 반드시 넘어 뜨려야하는 도미노가 될수밖에없습니다.

 

소스코드:

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> adj;
vector<int> check,finish,st;
int id;
int color;
void input(){
	cin>>n>>m;
	adj = vector<vector<int>>(n+1);
	check = finish = vector<int>(n+1);
	st.clear();
	int a,b;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		adj[a].push_back(b);
	}
	id = color=0;
}

int scc(int cur){
	check[cur]=++id;
	st.push_back(cur);
	int parent = check[cur];
	for(int next : adj[cur]){
		if(!check[next])parent = min(parent,scc(next));
		else if(!finish[next]) parent= min(parent,check[next]);
	}
	if (parent==check[cur]){
		color++;
		while(true){
			int node = st.back();
			st.pop_back();
			finish[node]=color;
			if(node==cur)break;
		}
	}
	return parent;
}

void solve(){
	for(int i=1;i<=n;i++){
		if(!check[i])scc(i);
	}
	vector<int> indegree(n+1);
	int res =0;
	for(int i=1;i<=n;i++){
		for(int next:adj[i]){
			indegree[finish[next]]|=finish[i]!=finish[next];
		}
	}
	for(int i=1;i<=color;i++)res+=!indegree[i];
	cout<<res<<"\n";
}
int main ()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	int test;
	cin>>test;
	while(test--){
		input();
		solve();
	}
}

 

궁금한점 혹은 모르는점 논리적인 오류등

어떤 질문이든 댓글은 언제나 환영입니다.