백준 6543번 그래프의 싱크

사용한 알고리즘 : SCC

​

bottom(G) = {v ∈ V: ∀w ∈ V, (v→w) ⇒ (w→v)} 를 만족하는 v 들을 찾는 것이 문제였습니다.

즉 각 점들을 SCC 로 묶어서, outdegree (다른 SCC로 가는 edge 수) 가 0 인 SCC 를 찾으면 됐습니다.

먼저 DFS라는 함수를 만들어 SCC 를 만들어 주었습니다.

이후 모든 점들을 보면서,

어떤 점에서 그 점의 자손들(adj로 정리 해둔 자손들)이 자신과 같은 SCC 안에 있지 않은 경우,

그 점이 포함된 SCC (코드상 sn[i] : i가 속한 SCC) 의 outdegree++ 해주는 개념으로

그냥 해당 SCC를 없애버렸습니다.

(우리의 목적은 outdegree가 0인 SCC를 찾는 것이기 때문에 outdegree가 하나라도 있으면 답이 될 수 없다고 생각했습니다.)

​

이후 남은 SCC 들을 정렬하여 답을 냈습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 5000;
	int n, m, cnt, SN, sn[MAX], dfsn[MAX];
	vector<int> adj[MAX];
	bool finished[MAX];
	stack<int> S;
	vector<vector<int>> SCC;
	int DFS(int curr){
	dfsn[curr] = ++cnt;
	S.push(curr);
	int result = dfsn[curr];
	for (int next: adj[curr]){
	if(dfsn[next] == 0) result = min(result, DFS(next));
	else if(!finished[next]) result = min(result, dfsn[next]);
	}
	if(result == dfsn[curr]){
	vector<int> currSCC;
	while(1){
	int t = S.top();
	S.pop();
	currSCC.push_back(t);
	finished[t] = true;
	sn[t] = SN;
	if(t==curr) break;
	}
	sort(currSCC.begin(), currSCC.end());
	SCC.push_back(currSCC);
	SN++;
	}
	return result;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(1){
	cin >> n;
	if(n==0) break;
	cin >> m;
	cnt = 0;
	SCC.clear();
	SN = 0;
	while(!S.empty()) S.pop();
	for (int i = 0; i < n; ++i) adj[i].clear();
	memset(finished,false,sizeof(finished));
	memset(dfsn,0,sizeof(dfsn));
	memset(sn,-1,sizeof(sn));
	for (int i = 0; i < m; ++i){
	int a, b;
	cin >> a >> b;
	adj[a-1].push_back(b-1);
	}
	for (int i = 0; i < n; ++i)
	if(dfsn[i]==0) DFS(i);
	for (int i = 0; i < n; ++i){
	for (int j = 0; j < adj[i].size(); ++j){
	if(sn[i]!=sn[adj[i][j]]) SCC[sn[i]].clear();
	}
	}
	sort(SCC.begin(),SCC.end());
	for (int i = 0; i < SCC.size(); ++i){
	if(!SCC[i].empty()){
	for (int j = 0; j <SCC[i].size(); ++j)
	cout << SCC[i][j]+1 << ' ';
	}
	}
	cout << '\n';
	}
	return 0;
	}

view raw BOJ 6543.cpp hosted with ❤ by GitHub