[백준] 6543 그래프의 싱크

문제

방향 그래프 G = (V, E)가 주어져 있다.

임의의 노드 u, v ∈ V에 대해서 u에서 v로 E에 포함된 간선만을 이용해 갈 수 있는 경로가 있으면 u→v로 표현한다.

만약 어떤 노드 v ∈ V가 자신으로부터 도달할 수 있는 모든 노드로부터 돌아오는 경로가 있다면, 즉 다음 조건을 만족한다면 노드 v ∈ V를 싱크라고 부른다.

• 조건: ∀w ∈ V, (v→w) ⇒ (w→v)

또한, 그래프 G의 싱크를 모아놓은 집합을 bottom(G)로 표현한다.

• bottom(G) = {v ∈ V: ∀w ∈ V, (v→w) ⇒ (w→v)}

주어진 그래프 G=(V, E)의 bottom(G)를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫 줄에는 노드의 수 n (1 ≤ n ≤ 5,000)과 음이 아닌 정수 m (0 ≤ m ≤ 100,000)이 주어진다. V = {1, 2, ..., n}이고, 간선의 수 |E|=m임을 의미한다.

그 다음부터는 각 간선을 나타내는 m쌍의 수 v1 w1 v2 w2 ... vm wm이 공백으로 구분되어 주어진다. 이는 (vi, wi) ∈ E를 의미한다.

마지막 줄에 0이 주어지고, 이 경우는 처리하지 않고 프로그램을 종료시켜야 한다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다.

 

그래프의 한 지점에서 도달할 수 있는 지점을 지나 다시 그 지점으로 돌아올 수 있을때 그 정점들을 묶어 하나의 강결합 컴포넌트,SCC라고 부릅니다.

 

어떤 노드로부터 도달할 수 있는 모든 지점이 한 SCC에 존재하면 싱크라고 합니다.

 

따라서, 타잔알고리즘으로 한 SCC로 묶은 후에, 모든 노드에 대해 도달할 수 있는 모든 노드가 한 SCC안에 존재하는지 확인하면 됩니다.

 

이때 도달할 수 있는 노드를 확인할때 bfs를 사용하는데, 그 노드들을 새로운 벡터에 저장하게된다면 만약 모든 노드가 하나의 scc에 존재할때, 배열의 크기는

4byte * 5000 * 5000 는 약 100mb에 근접하는데 이 문제의 조건은 100mb이므로 저장하면 안됩니다..

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int visited[5005];
vi adj[5001], st, can[5005];
int v[5005], s[5005], cnt, num, N, M;

int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = ++cnt;
	for (auto r : adj[k]) {
		if (!v[r]) {
			parent = min(parent, dfs(r));
		}
		else if (!s[r]) {
			parent = min(parent, v[r]);
		}
	}
	if (parent == v[k]) {
		num++;
		while (auto t = st.back()) {
			st.pop_back();
			s[t] = num;
			if (t == k)break;
		}
	}
	return parent;
}


int main() {
	FAST;
	while (1) {
		cnt = 0;
		num = 0;
		mset(v);
		mset(s);
		REP(i, 5000)adj[i].clear();
		REP(i, 5000)can[i].clear();
		cin >> N;
		if (!N)break;
		cin >> M;
		while (M--) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
		}
		REP(i, N) {
			if (!v[i])dfs(i);
		}
		REP(i, N) {
			mset(visited);
			bool flag = 1;
			visited[i] = 1;
			queue<int>q;
			q.push(i);
			while (!q.empty()) {
				if (!flag)break;
				auto cur = q.front();
				q.pop();
				for (int r : adj[cur]) {
					if (!visited[r]) {
						q.push(r);
						if (s[i] != s[r]) {
							flag = 0;
							break;
						}
						visited[r] = 1;
					}
				}
			}
			if (flag)cout << i << " ";
		}
		cout << "\n";
	}
}