[Baekjoon/C++] 2150번 - Strongly Connected Component

[백준] Baekjoon Online Judge

문제로 이동

 

문제

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

 

입력

첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.

정점은 1부터 V까지 번호가 매겨져 있다.

 

출력

첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

 

---

풀이

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

#define MAX 10001

int V, E, id;
int parent[MAX];
bool finish[MAX];		// scc 여부
vector<int> arr[MAX];	// 간선
vector<vector<int>> scc;
stack<int> st;

int dfs(int now);

int dfs(int now) {
	parent[now] = ++id;
	st.push(now);

	int p = parent[now];
	for (int n : arr[now]) {
		if (parent[n] == 0) p = min(p, dfs(n));		// 첫 방문인 정점
		else if (!finish[n]) p = min(p, parent[n]);	// 아직 scc가 되지 않은 정점
	}

	if (p == parent[now]) {
		vector<int> sc;

		// 찾은 집합을 scc에 추가하기
		while (true) {
			int t = st.top();
			st.pop();

			sc.push_back(t);
			finish[t] = true;

			if (t == now) break;
		}

		sort(sc.begin(), sc.end());

		scc.push_back(sc);
	}

	return p;
}

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

	cin >> V >> E;

	while (E--) {
		int a, b;
		cin >> a >> b;

		arr[a].push_back(b);
	}

	// scc 찾기
	for (int i = 1; i <= V; i++) {
		if (parent[i] == 0) dfs(i);
	}

	sort(scc.begin(), scc.end());

	// 출력
	cout << scc.size() << '\n';
	for (int i = 0; i < scc.size(); i++) {
		for (int n : scc[i]) cout << n << ' ';
		cout << "-1\n";
	}

	return 0;
}

 타잔 알고리즘으로 문제를 풀었다.

 

int dfs(int now) {
	parent[now] = ++id;
	st.push(now);

	int p = parent[now];
	for (int n : arr[now]) {
		if (parent[n] == 0) p = min(p, dfs(n));		// 첫 방문인 정점
		else if (!finish[n]) p = min(p, parent[n]);	// 아직 scc가 되지 않은 정점
	}

	if (p == parent[now]) {
		vector<int> sc;

		// 찾은 집합을 scc에 추가하기
		while (true) {
			int t = st.top();
			st.pop();

			sc.push_back(t);
			finish[t] = true;

			if (t == now) break;
		}

		sort(sc.begin(), sc.end());

		scc.push_back(sc);
	}

	return p;
}

 깊이 우선 탐색을 통해 scc를 만드는 함수이다. 하나의 scc에 속한 정점은 다른 scc에 속하지 못하기에 finish[]로 scc가 된 정점을 체크해야 한다. 탐색이 끝나고 만든 집합을 scc에 넣을 때 해당 집합을 오름차순으로 정렬한다.

 

참고

타잔 알고리즘

해당 블로그로 타잔 알고리즘을 공부했다.