[백준] 4196 - 도미노

https://www.acmicpc.net/problem/4196

4196번: 도미노

 

SCC를 연습하고 있던 중에 발견한 흥미로운 문제이다.

 

도미노의 특성상 하나의 도미노를 쓰러트리면 다른 도미노도 쓰러질 수 있기 때문에 SCC를 찾아야 한다.

그런데 여기서 끝나는 것이 아니다. 바로 하나의 SCC는 다른 SCC에 영향을 줄 수 있다.

 

만약

1 -> 2, 2 -> 3, 3 -> 1, 4 -> 3, 5 -> 4

같은 경우에서 

SCC는 {1, 2, 3}, {4}, {5}이지만 5번 도미노 하나만 쓰러트리면 모든 도미노를 쓰러트릴 수 있다.

 

이 사실을 알고 위상 정렬을 생각했다. 하지만 일반적인 정점 간의 위상 정렬은 사이클이 있는 그래프에서는 성립되지 못한다 => SCC 간의 위상 정렬을 사용한다.

 

즉, {1, 2, 3}, {4}, {5}를 각각 SCC1, SCC2, SCC3이라 하고 위상 정렬을 수행하면

{5} -> {4} -> {1, 2, 3} 이 되어서 indegree = 0 인 5번 도미노 하나만 쓰러트리면 된다는 사실을 알 수 있다.

 

따라서 해당 문제에서는 각 SCC마다 idx를 매겨주고, SCC간의 연결을 탐색해 indegree = 0인 도미노의 개수가 최종 답이 된다.

 

결론적으로 SCC + 위상 정렬 문제였다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
vector<vector<int>> v;
vector<int> s;
int visit[100001], scc[100001], inp[100001];
int id = 1, ans, sccIdx = 1;

int dfs(int idx) {
	int ret = visit[idx] = id++;
	s.push_back(idx);
	for (auto i : v[idx]) {
		if (!visit[i]) {
			ret = min(ret, dfs(i));
		}
		else if (!scc[i]) {
			ret = min(ret, visit[i]);
		}
	}

	if (ret == visit[idx]) {
		while (1) {
			int t = s.back();
			scc[t] = sccIdx;
			s.pop_back();
			if (t == idx)break;
		}
		sccIdx++;
	}
	return ret;
}

int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		v.resize(n + 1);
		for (int i = 0; i < m; i++) {
			int a, b; cin >> a >> b;
			v[a].push_back(b);
		}
		for (int i = 1; i <= n; i++) {
			if (!scc[i])dfs(i);
		}
		for (int i = 1; i <= n; i++) {
			for (auto j : v[i]) {
				if (scc[i] != scc[j]) {
					inp[scc[j]]++;
				}
			}
		}
		for (int i = 1; i < sccIdx; i++) {
			if (inp[i] == 0)ans++;
		}
		cout << ans << '\n';

		memset(visit, 0, sizeof(visit));
		memset(scc, 0, sizeof(scc));
		memset(inp, 0, sizeof(inp));
		id = 1; sccIdx = 1; ans = 0;
		v.clear(); s.clear();
	}
	return 0;
}