[알고리즘] Graph (3) - Strongly connected components(SCC)

[3. Strongly connected conponents]

1. 방향그래프의 연결관계 connected

  → 방향 그래프에서 노드 v와 노드 u가 서로에게 도달할 수 있는 경로가 존재할 때, 두 노드는 연결되어 있는 상태

2. SCC 집합

  → 개체들을 상호 연결 관계에 따라 개체끼리 집합으로 분류

  → SCC내의 모든 노드들은 서로 도달할 수 있음

  → 위 그래프의 SCC : {A}, {B, E}, {C, F}, {D}, {G, H, I, J, K, L}

 

3. SCC의 성질

(1) SCC로 만든 방향그래프는 dag이다.

(2) 깊이우선탐색에서 가장 높은 post number를 갖는 노드는 SCC로 만든 그래프의 source에 위치해야 한다.

(3) SCC인 C와 C'가 있을 때 C에서 C'로 향하는 간선이 있다면, C에 있는 가장 높은 post number가 C'에 있는 가장 높은 post number보다 크다.

(4) 어느 vertex에서 시작하든 관계없이 SCC는 동일하다

 

4. SCC찾기

(1) 주어진 그래프G의 역방향 그래프 G'를 도출한다

(2) G'를 DFS방식으로 탐색한다

(3) G'의 sink를 찾아 제거한다

(4) G'의 sink가 곧 G의 SCC

Ex)

(1) 주어진 그래프의 역방향 그래프 도출

(2) DFS 탐색

(3) G'의 sink를 찾고 제거하는 과정 반복 (가장 높은 post number부터)

   : {L}, {K}, {G, F, G, H, I}, {J}, {A}, {B, D, E}

(4) G'의 sink가 곧 G의 SCC

3. 구현

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> g[10001];
vector<int> gr[10001];
int pre[10001], post[10001];
queue<int> scc;
vector<pair<int, int>> sorted;

int clock = 0;

void initVisit() {
	clock = 0;
	for (int i = 0; i < 10001; i++)
		pre[i] = post[i] = -1;
}

void DFS(int v) {
	printf("%d visiting \n", v);
	pre[v] = clock++;

	for (int i = 0; i < gr[v].size(); i++)
		if (pre[gr[v][i]] < 0)
			DFS(gr[v][i]);
	post[v] = clock++;
	//post[v], v 저장
	sorted.push_back(make_pair(post[v], v));
}

void DFS2(int v) {
	pre[v] = clock++;
	scc.push(v);

	for (int i = 0; i < g[v].size(); i++)
		if (pre[g[v][i]] < 0)
			DFS2(g[v][i]);
}

int main() {
	//1. 방향그래프 생성
	int v, e, u, w;
	FILE* fp = fopen("graph.txt", "r+t");
	fscanf(fp, "%d %d", &v, &e);
	for (int i = 0; i < e; i++) {
		fscanf(fp, "%d %d", &u, &w);
		g[u].push_back(w);
	}
/* 직접 입력받기
	int v, e;	//v=개체의 수, e=간선의 수
	scanf("%d %d", &v, &e);
	int u, w;	//간선, u -> w
	for (int i = 0; i < e; i++) {
		scanf("%d %d", &u, &w);		
		g[u].push_back(w);
	}
*/
/* 그래프 확인
	for (int i = 1; i <= v; i++) {
		printf("[%d]", i);
		for (int j = 0; j < g[i].size(); j++)
			printf("->%d, ", g[i][j]);
		printf("\n");
	}
*/
	//2. 그래프의 역방향 그래프 만들기
	for (int i = 1; i <= v; i++)
		for (int j = 0; j < g[i].size(); i++)
			gr[g[i][j]].push_back(i);
	for (int i = 1; i <= v; i++)
		sort(gr[i].begin(), gr[i].end());


	//3. 역방향 그래프에서 DFS로 prenum postnum 계산하기
	initVisit();
	for (int i = 1; i <= v; i++) 
		if (pre[i] < 0)
			DFS(i);
/* pre, post 확인하기
	for (int i = 1; i < v; i++)
		printf("%d: %d, %d\n", i, pre[i], post[i]);
*/
	reverse(sorted.begin(), sorted.end());
/*
	for (int i = 0; i < v; i++)
		printf("[%d] %d, %d\n", i, sorted[i].first, sorted[i].second);
*/
		
	//4. 그래프에서 postnum의 역순으로 DFS통해 SCC도출
	//4.1 postnum의 역순으로 dfs
	initVisit();
	for (int i = 1; i <= v; i++) {
		if (pre[sorted[i].second] < 0) {
			DFS2(sorted[i].second);
			if (!scc.empty()) {
				printf("scc: ");
				while (!scc.empty()) {
					printf("%d ", scc.front());
					scc.pop();
				}
				printf("\n");
			}
		}
	}
	return 0;
}