boj, 백준) 2150. SCC(Strongly Connected Component)

1. 문제 링크

www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

 

2. 문제 개요

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

 

3. 문제 힌트

코사라주 알고리즘(kosaraju's algorithm), 타잔 알고리즘(Tarjan's algorithm)을 사용하여 SCC를 선형시간에 구함.

 

4. 문제 풀이

결국 알고리즘을 알아야 풀 수 있는 문제이다.

 

(1) 코사라주 알고리즘

 코사라주 알고리즘은

주어진 그래프 G,

그래프 G의 간선들을 모두 역방향으로 한 그래프 G`,

DFS탐색이 끝난 순서로 담긴 Stack이 필요하다.

 

그래프 G를 사용한 DFS -> Stack에 쌓인 순서대로 그래프 G`를 사용한 DFS탐색을 통해 SCC를 구한다.

그래프 G와 Stack은 역방향 그래프 G`에서 탐색할 순서를 지정한다.

그래프 G`에서 위의 순서로 DFS했을 때, 각 DFS마다 정점을 최초로 방문하는 모든 정점들은 같은 SCC라고 할 수 있다.

 

알고리즘 자체나, 혹은 이게 왜 SCC를 나타내는지, 증명은 다른 블로그에서 훌륭하신 분들이 작성해 놓았으니 참고해주시기 바랍니다.

 

예를 들면,, 왜 DFS를 탐색이 끝난 순서대로 stack에 삽입할까..? 에 대한 의문을 가질 수 있겠다.

 

시간 복잡도는 O(V+E)이다.(계수는 없지만, DFS를 2번 한다는 점. 참고.)

 

(2) 타잔 알고리즘

코사라주 알고리즘과는 다르게 단 한 번의 DFS만으로 SCC를 구하는 알고리즘

 

주목할만한 점은 각 정점의 방문 순서대로 정수 값을 1씩 증가시켜 나간다는 점, 역방향 간선, 교차 간선 등을 고려한다는 점.

 

각 정점마다 정수값을 저장할 배열 1개(visited으로도 사용 가능, 이분매칭과 같은 느낌)

scc에 이미 추출 되었는지 검사할 bool 배열 1개,

이번엔 방문 하자마자 삽입되는 stack,

 

 

DFS를 시작하는데,

자신의 자손들이 자신의 조상으로 갈 수 있는 경우가 하나도 없는 경우, 즉, 반환되는 값이 자기 자신과 같다면, 그때는 scc추출을 시작해줍시다.

stack에서 자기자신이 나올 때까지 pop 합니다.

 

역방향 간선을 구분하는 방법은 '방문함 && SCC가 아님'으로 판단할 수 있습니다.

일반적으로 연결되어 있는 간선은 '방문하지 않음'을 통해서 알 수 있습니다.(일반적인 DFS)

 

이 경우도 시간 복잡도는 O(V+E)입니다.

 

단순한 문제 풀이가 아닌 알고리즘 자체에 대해 공부하고자 하신다면 이 글은 설명이 부족합니다.

다른 알고리즘에 비해서 설명이 복잡하기 때문에 잘 정리해놓은 다른 블로그를 참고해주시기 바랍니다 :)

 

5. 코드

(1) 코사라주 알고리즘

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<vector<int>> adj, ans;
vector<vector<int>> reverse_adj;
vector<bool> visited;
stack<int> s;
int v, e, num;
 
void reverse_dfs(int cur) {
 
	if (visited[cur])
		return;
 
	visited[cur] = true;
	ans[num].push_back(cur);
 
	for (int next : reverse_adj[cur])
		reverse_dfs(next);
 
	return;
}
 
void dfs(int cur)
{
	if (visited[cur])
		return;
 
	visited[cur] = true;
 
	for (int next : adj[cur])
		dfs(next);
 
	s.push(cur);
	return;
}
 
int main()
{
	scanf("%d %d", &v, &e);
 
	adj.resize(v + 1);
	reverse_adj.resize(v + 1);
	visited.resize(v + 1, false);
 
	for (int i = 0; i < e; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
 
		adj[from].push_back(to);
		reverse_adj[to].push_back(from);
	}
 
	for (int i = 1; i <= v; ++i)
		dfs(i);
 
	fill(visited.begin(), visited.end(), false);
 
	while (!s.empty()) {
		if (!visited[s.top()]) {
			ans.push_back(vector<int>());
			reverse_dfs(s.top());
			++num;
		}
		s.pop();
	}
 
	printf("%d\n", ans.size());
 
	for (int i = 0; i < ans.size(); ++i) 
		sort(ans[i].begin(), ans[i].end());
	sort(ans.begin(), ans.end());
 
	for (int i = 0; i < ans.size(); ++i) {
		for (int j = 0; j < ans[i].size(); ++j) {
			printf("%d ", ans[i][j]);
		}
		printf("-1\n");
	}
 
	return 0;
}

 

(2) 타잔 알고리즘

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<vector<int>> adj, ans;
vector<int> dfsn;
vector<bool> finished;
stack<int> s;
int n, e, cnt;
 
int dfs(int cur)
{
	dfsn[cur] = ++cnt;
	s.push(cur);
 
	int ret = dfsn[cur];
 
	for (int next : adj[cur])
	{
		if (dfsn[next] == 0)
			ret = min(ret, dfs(next));
		else if (!finished[next])	//역방향 간선
			ret = min(ret, dfsn[next]);
	}
 
	//자신, 자손들을 포함해서 갈 수 있는 최대의 조상이 자기 자신인 경우 SCC추출 시작.
	if (ret == dfsn[cur]) {
		vector<int> scc;
 
		while (1) {
			int val = s.top(); s.pop();
			scc.push_back(val);
			finished[val] = true;
			if (val == cur)
				break;
		}
		ans.push_back(scc);
	}
	return ret;
}
 
int main()
{
	scanf("%d %d", &n, &e);
 
	adj.resize(n + 1);
	dfsn.resize(n + 1);
	finished.resize(n + 1);
 
	for (int i = 0; i < e; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
 
		adj[from].push_back(to);
	}
 
	for (int i = 1; i <= n; ++i)
		if(dfsn[i] == 0)
		dfs(i);
 
	for (int i = 0; i < ans.size(); ++i)
		sort(ans[i].begin(), ans[i].end());
	sort(ans.begin(), ans.end());
 
	printf("%d\n", ans.size());
 
	for (int i = 0; i < ans.size(); ++i) {
		for (int j = 0; j < ans[i].size(); ++j)
			printf("%d ", ans[i][j]);
		printf("-1\n");
	}
	
	
 
	return 0;
}

 

 

6. 결과