(BOJ) 6543 그래프의 싱크

문제: https://www.acmicpc.net/problem/6543

 

문제 설명:

bottom(G) 어떤 정점에서 출발하여 갈 수 있는 모든 정점에서 돌아 올 수 있는 정점들의 집합

 

ex) 

5 5

1 2 2 3 3 1 3 4 4 5

 

1->2->3->1로 1,2,3이 bottom(G) 속할 것 같아 보이지만

3->4->5로 가고 4나 5에서 1,2,3으로 올 수 없으므로 bottom(G)에 속하지 않음

5는 출발한 정점이 없으므로 bottom(G)에 속함

 

문제 풀이:

알고리즘 - scc

1. dfs 돌려서 정점 stack에 쌓기

2. scc를 저장하는데

현재까지 저장된 res(scc)의 크기가 t라고 했을 때, 지금 rdfs를 돌려서 얻은 scc는 res[t]이후에 쌓이게 된다

그러므로 한 번 scc 돌리고 그 전 위치 t부터 포문을 돌리면서 현재 scc에 속하는 정점에서 scc에 속하지 않는 정점으로 가는 간선을 가진 정점이 있다면 현재 scc는 전부 bottom(G)에 속하지 않으므로 pop해준다

3. 마지막까지 남은 scc를 저장한 res를 sorting해서 출력  

 

 

소스 코드:

vector<vector<int>> adj, adj2;
vector<int> res;
int n, m,pos;
bool visit[5001];
stack<int> st;

void dfs(int v) {
	visit[v] = true;
	for (int i : adj[v]) {
		if (visit[i]) continue;
		dfs(i);
	}
	st.push(v);
}
void rdfs(int v) {
	visit[v] = true;
	res.push_back(v);
	for (int i : adj2[v]) {
		if (visit[i]) continue;
		rdfs(i);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	while (1) {
		cin >> n;
		if (n == 0) break;
		cin >> m;

		pos = 0;
		adj.clear();
		adj2.clear();
		res.clear();
		adj.resize(n + 1);
		adj2.resize(n + 1);
		memset(visit, false, sizeof(visit));
		for (int i = 0; i < m; i++) {
			int q, w;
			cin>>q>>w;
			adj[q].push_back(w);
			adj2[w].push_back(q);
		}
		for (int i = 1; i <= n; i++) {
			if(!visit[i]) dfs(i);
		}
		memset(visit, false, sizeof(visit));
		
		while (!st.empty()) {
			int cur = st.top();
			st.pop();
			if (visit[cur]) continue;
			int t = res.size();
			rdfs(cur);

			bool chk = true;
			for (int i = t; i < res.size(); i++) {
				int len = adj[res[i]].size();
				for (int j = 0; j < len; j++) {
					if (!visit[adj[res[i]][j]]) {
						chk = false;
						break;
					}
				}
				if (!chk) break;
			}
			if (!chk) {
				while (res.size() > t) {
					res.pop_back();
				}
			}
		}
		sort(res.begin(), res.end());
		int len = res.size();
		for (int i = 0; i < len; i++) {
			cout << res[i] << " ";
		}

		cout << "\n";
	}
	return 0;
}