[백준] 4196 도미노

문제

도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.

이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

 

 

 

도미노 x가 넘어질때 y가 넘어지는 관계가 주어질때,

x>>y>>z>>x 같이 사이클이 발생하면 x,y,z,중 하나라도 넘어지면 모두 넘어지게 됩니다.

따라서 그래프가 주어질때, scc끼리 묶는다면 단방향간선그래프가 그려지는데

이때 위상정렬되어 하나도 들어오지 않는 scc만 넘어뜨린다면

모든 도미노를 넘어뜨릴 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
int TC, N, M, v[100001], s[100001], num = 0, cnt = 0;
vector<int>adj[100001];
vector<int>st;
vector<vector<int>>scc;
int p[100001];
vector<int>domino[100001];
int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = k;
	for (auto r : adj[k]) {
		if (!v[r]) {
			parent = min(parent, dfs(r));
		}
		else if (!s[r]) {
			parent = min(parent, v[r]);
		}
	}
	if (parent == v[k]) {
		num++;
		vector<int>temp;
		while (1) {
			auto r = st.back(); st.pop_back();
			temp.push_back(r);
			s[r] = num;
			if (r == k)break;
		}
		scc.push_back(temp);
	}
	return parent;
}
void tarjan() {
	for (int i = 1; i <= N; i++) {
		if (!v[i])dfs(i);
	}
}
int main() {
	cin >> TC;
	while (TC--) {
		memset(v, 0, sizeof(v));
		memset(s, 0, sizeof(s));
		cnt = 0;
		for (int i = 1; i <= 100000; i++) {
			adj[i].clear();
			domino[i].clear();
		}
		num = 0;
		st.clear();
		scc.clear();
		memset(p, 0, sizeof(p));
		//초기화

		cin >> N >> M;
		int x, y;
		while (M--) {
			cin >> x >> y;
			adj[x].push_back(y);
		}
		tarjan(); //타잔알고리즘으로 scc별로 묶습니다.

		for (int i = 1; i <= N; i++) {
			for (auto r : adj[i]) {
				if (s[i] != s[r]) { 
					p[s[r]]++; //scc별로 들어오는게 있으면 +1
				}
			}
		}

		int ans = 0;
		for (int i = 1; i <= num; i++) {
			if (!p[i])ans++; //들어오지 않는 scc만 넘어뜨리면 됩니다.
		}
		cout << ans << "\n";
	}

}