[BAE/<JOON> 문제풀이] 4196. 도미노

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

4196번: 도미노

서론

SCC + 토폴로지 소트? 문제

SCC끼리 진입 간선 개수가 0인 SCC의 개수를 세면 된다.

---

풀이

처음에는 단순히 진입 간선이 0인 정점을 세는 문젠 줄 알았는데 도미노 배열에서 순환이 있어도 반드시 1개는 쓰러트려야 전체가 쓰러지므로 SCC 문제였다.

 

별도의 직관이나 추론 없이 알고리즘 원형만 사용해도 풀리는 문제라 풀이 과정에 딱히 쓸게 없다.

---

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct pa {
	ll sum, cnt;
};
struct pos {
	short x, y, s, c = 0;
};
struct cmp {
	bool operator()(pos a, pos b) {
		return a.c > b.c;
	}
};
int n, m; vector<vector<int>> arr, scclist; stack<int> st; vector<int> spos, poslist, vis, iscc;
int cnt = 1;
int dfs(int x) {
	vis[x] = true;
	poslist[x] = cnt++;
	st.push(x);
	int mp = poslist[x];
	for (auto v : arr[x]) {
		if (!vis[v]) {
			int ret = dfs(v);
			mp = ret < mp ? ret : mp;
		}
		else if (iscc[v] == 0) {
			mp = mp < poslist[v] ? mp : poslist[v];
		}
	}
	if (poslist[x] == mp) {
		vector<int> scc;
		while (!st.empty() && st.top() != x) {
			scc.push_back(st.top());
			spos[st.top()] = scclist.size();
			iscc[st.top()] = 1;
			st.pop();
		}
		scc.push_back(st.top());
		spos[st.top()] = scclist.size();
		iscc[st.top()] = 1;
		st.pop();
		scclist.push_back(scc);
	}
	return poslist[x] = mp;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		cin >> n >> m; arr = vector<vector<int>>(n + 1); scclist = vector<vector<int>>(); st = stack<int>(); spos = poslist = vis = iscc = vector<int>(n + 1);
		cnt = 1;
		for (int i = 1; i <= m; i++) {
			int s, e; cin >> s >> e;
			arr[s].push_back(e);
		}
		for (int i = 1; i <= n; i++) {
			if (vis[i] == 0) {
				dfs(i);
			}
		}
		vector<int> en(scclist.size());
		for (int i = 1; i <= n; i++) {
			for (auto nx : arr[i]) {
				if (spos[nx] == spos[i]) continue;
				en[spos[nx]]++;
			}
		}
		int d = 0;
		for (int sp : en) {
			if (sp == 0) {
				d++;
			}
		}
		cout << d << "\n";
	}
	return 0;
}