BOJ 4196 - 도미노 (유니온 파인드로 저장)

https://www.acmicpc.net/submit/4196/14605274

로그인

 

심심해서 유니온파인드로 scc를 저장해봤다.

 

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define MAX 100001
using namespace std;

int id, dfsn[MAX];
bool finished[MAX];
vector<int> adj[MAX];

int sn[MAX],SN;

int find(int a) {
	if (sn[a] == a) return a;
	return sn[a] = find(sn[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	sn[a] = b;
}

int makeSCC(int curr, stack<int> &s) { //dfs로scc추출, base::1
	dfsn[curr] = ++id;
	s.push(curr);

	int parent = dfsn[curr];
	for (int next : adj[curr]) {
		if (dfsn[next] == 0) parent = min(parent, makeSCC(next,s));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}
	if (parent == dfsn[curr]) {
		int uf = s.top();
		while (1) {
			int t = s.top();
			s.pop();
			merge(uf, t);
			finished[t] = true;
			if (t == curr) break;
		}
		SN++;
	}

	return parent;
}

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

	int tc; cin >> tc;
	while (tc--) {
		int n, m; cin >> n >> m;
		for (int i = 1; i <= MAX; i++) {
			sn[i] = i;
			adj[i].clear();
		}
		id = SN = 0;
		fill(dfsn, dfsn + MAX, 0);
		fill(finished, finished + MAX, false);
		
		for (int i = 0, u, v; i < m; i++) {
			cin >> u >> v;
			adj[u].push_back(v);
		}
		stack<int> s;
		for (int i = 1; i <= n; i++)
			if (dfsn[i] == 0) makeSCC(i,s);

		int sInd[MAX] = { 0 }; //SCC의 크기만큼의 배열
		for (int i = 1; i <= n; i++)
			for (int j : adj[i])
				if (find(i) != find(j)) 
					sInd[find(j)]++;

		int rst = 0;
		bool flag[MAX] = { 0 };
		for (int i = 1; i <= n; i++) {
			if (flag[find(i)]) continue;
			if (sInd[find(i)] == 0) {
				rst++;
				flag[find(i)] = true;
			}
		}

		cout << rst << '\n';

	}
}

 

SN, sn[MAX] 사용하는게 훨씬 편한 것 같다