(백준 4196번 도미노) (라이님 블로그 대회 알고리즘 따라잡기 22) SCC

백준 4196번

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

 

SCC를 푸는 것에 추가해서 SCC 하나를 하나의 노드로 보고 indegree가 0인 SCC의 갯수를 세는 문제!

 

라이님 블로그에서 풀이를 열심히 공부해서 내 식대로 바꿔보았다.

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220802519976&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

 

정말 많이 틀렸는데..

 

대부분의 문제는 노드를 입력 그대로 받아서 생겼다..

(보통 문제에서는 점이 1, 2, 3 ... 으로 주어지지만, 프로그래밍은 0, 1, 2...로 하니까..)

그래서 for loop을 돌 때 i = 0부터 돌린 부분이 모두 뻑이 나서.. 고생을 살짝 했다ㅎㅎ

 

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;

constexpr int MAX = 100001;

int id = 0, disc[MAX], SN = 0, sn[MAX], sIndegree[MAX];
bool finished[MAX];
vector<int> adj[MAX];
vector<vector<int>> sccs;
stack<int> st;



int dfs(int u) {
	disc[u] = ++id;
	int parent = disc[u];
	st.push(u);

	for (int v : adj[u]) {
		if (disc[v] == 0) parent = min(parent, dfs(v));
		else if (!finished[v]) parent = min(parent, disc[v]);
	}

	if (disc[u] == parent) {
		vector<int> scc;
		while (true) {
			int t = st.top();
			st.pop();
			scc.push_back(t);
			finished[t] = true;
			sn[t] = SN;
			if (u == t) break;
		}
		sccs.emplace_back(scc);
		SN++;
	}
	return parent;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t; cin >> t;

	while (t--) {
		memset(disc, 0, sizeof(disc));
		memset(sn, 0, sizeof(sn));
		memset(sIndegree, 0, sizeof(sIndegree));
		memset(finished, 0, sizeof(finished));
		while (!st.empty()) st.pop();
		sccs.clear();

		id = 0; SN = 0;

		int N, M;
		cin >> N >> M;

		for (int i = 1; i <= N; i++) {
			adj[i].clear();
		}

		for (int i = 0; i < M; i++) {
			int x, y; cin >> x >> y;
			adj[x].push_back(y);
		}
		
		for (int i = 1; i <= N; i++) {
			if (disc[i] == 0) dfs(i);
		}

		int ans = 0;

		

		for (int i = 1; i <= N; i++) {
			for (int j : adj[i]) {
				if (sn[i] != sn[j]) sIndegree[sn[j]]++;
			}
		}


		for (int i = 0; i < SN; i++) {
			if (sIndegree[i] == 0) ans++;
		}

		cout << ans << "\n";

	}

	return 0;
}