[백준 6543] 그래프의 싱크

문제 링크 => 6543번: 그래프의 싱크 (acmicpc.net)

6543번: 그래프의 싱크

---

SCC를 활용한 문제이다.

 

SCC에 대한 vector들의 정보들을 v1, v2, v3, ... ,vt 라고 하자.

 

이때 v1의 size값이 v1에 존재하는 정점들에 대해서 SCC로 묶인 정점들로만 이동 가능한지를 파악하면 끝이다.

 

자세한 설명을 위해 예제 입력 1을 살펴보도록 한다.

 

ex) 1 => 3, 2 => 3, 3 => 1 으로 주어진 그래프에 대하여 SCC는 다음과 같이 묶인다.

 

v1 : 1, 3

v2 : 2

 

이때, v1 의 size는 2이고 정점 1, 3은 1, 3 으로만 이동되므로 성립한다.

 

그러나 v2 의 size는 1이고 정점 2는 2 로만 이동되지 않는다. (2 => 3으로 가는 경우가 생김)

 

따라서 정점 2는 size와 SCC로 묶인 정점으로만 이동하지 않으므로 bottom이 아니고 나머지 정점들은 전부 bottom이다.

 

ex) 1 => 2 으로 주어진 그래프에 대하여 SCC는 다음과 같이 묶인다.

 

v1 : 1

v2 : 2

 

이때, v1 의 size는 1이고 정점 1은 1 로만 이동되지 않는다. (1 => 2으로 가는 경우가 생김)

 

그러나 v2 의 size는 1이고 정점 2는 자기 자신만 해당되며 이동하는 경우가 없다. (2에서 다른곳으로 이동하는 경우가 없음)

 

따라서 size값이 1일 경우 다른 정점으로 이동하지 않을 경우에는 bottom 이 되는 것을 알 수 있다.

 

소스 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int n, m;
vector<int> go[5001], back[5001];
bool visited[5001];
stack<int> s;
vector<int> v;
vector<vector<int>> res;

void dfs1(int x) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < go[x].size(); i++) {
		int next = go[x][i];
		dfs1(next);
	}
	s.push(x);
}

void dfs2(int x) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < back[x].size(); i++) {
		int next = back[x][i];
		dfs2(next);
	}
	v.push_back(x);
}

int is_Bottom(vector<int> vv) {
	vector<int> tmp;
	queue<int> q;
	q.push(vv[0]);
	visited[vv[0]] = true;
	tmp.push_back(vv[0]);
	int op = vv.size()-1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < go[x].size(); i++) {
			int next = go[x][i];
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
				op--;
				tmp.push_back(next);
			}
		}
		if (op < 0) {
			for (int i = 0; i < tmp.size(); i++) {
				visited[tmp[i]] = false;
			}
			return 0;
		}
	}

	for (int i = 0; i < tmp.size(); i++) {
		visited[tmp[i]] = false;
	}
	return 1;
}

void all_Initialize() {
	v.clear();
	res.clear();

	for (int i = 1; i <= n; i++) {
		go[i].clear();
		back[i].clear();
		visited[i] = false;
	}
}

void initialize() {
	for (int i = 1; i <= n; i++) {
		visited[i] = false;
	}
}

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

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

		if (m == 0) {
			for (int i = 1; i <= n; i++) {
				cout << i << " ";
			}
			continue;
		}

		all_Initialize();

		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			go[x].push_back(y);
			back[y].push_back(x);
		}

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				dfs1(i);
			}
		}

		initialize();

		while (!s.empty()) {
			int x = s.top();
			s.pop();
			if (!visited[x]) {
				dfs2(x);
				res.push_back(v);
				v.clear();
			}
		}

		initialize();

		for (int i = 0; i < res.size(); i++) {
			if (is_Bottom(res[i])) {
				for (int j = 0; j < res[i].size(); j++) {
					v.push_back(res[i][j]);
				}
			}
		}

		sort(v.begin(), v.end());
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << endl;
	}

	return 0;
}