[BOJ2150] Strongly Connected Component

[BOJ2150] Strongly Connected Component

문제 링크

문제 설명

• 문제 설명은 따로 없다.

• SCC를 찾아서 그 안에 있는 정점들을 정렬하여 출력하고 마지막에 -1을 붙혀주면 된다.

SCC(강한연결성분)란?

• 먼저 SCC는 Bi Component와 달리 방향그래프에서 존재하며, Bi Component가 에지의 집합으로 분할하였다면, SCC는 정점의 집합으로 분할 한다.

• 연결 성분 이란 연결되어있는 부분 그래프 중 그것을 포함하고, 다른 정점까지 포함할 경우 틀이 깨지는 것을 말한다. 즉, 연결되어있는 부분 그래프 중 극대의 개념까지 포함되어있다.

• SCC는 직역하면 강한 연결 성분 으로, 방향그래프에서 강한 연결 성분 내부에 있는 vertex 쌍 간에는 경로가 존재한다.

• 서로 다른 강한 연결 성분에 있는 vertex 끼리는 한 vertex에서 다른 vertex로 갈 수는 있지만 역의 경우는 성립하지 않는다.

• DFS tree에서 같은 SCC 끼리는 한 곳에 모여서 존재하기 때문에, DFS 탐색을 하며 스택에 저장하다가, SCC의 리더를 발견하고 리더까지 POP을 하면 하나의 SCC가 모여진다.

• 리더를 찾는 것이 핵심 이다.

SCC의 리더는 어떻게 찾을 것인가?

• DFS를 진행할 때, discover_time과 finish_time을 같이 구하며 진행한다.

• 초기 lowlevel은 나의 discover_time으로 초기화 해둔다.

• 정점 v에 인접한 정점을 w라고 할 때, backedge의 경우, v의 lowlevel과 w의 discover_time중 작은 값을 v의 lowlevel에 저장 한다.

• forward 에지는 신경쓰지 않아도된다.

• cross에지 의 경우, v->w 일 때 항상 w의 색상은 black 으로 보일 것이며 (w에서 진행한 dfs는 모조리 완료되었다는 뜻) w가 어떤 scc에 이미 속해있는 상황이라면 v는 절대 w가 속해있는 scc에 속하지 않을 것이므로 이런 경우는 신경쓰지 않아도 된다. 반면 w가 아직 어떤 scc 그룹에도 속하지 못한 경우, w의 lowlevel은 w와 v의 LCA(Least Common Ancestor) 의 discover_time보다 작거나 같을 것 이기 때문에, v의 lowlevel과 w의 lowlevel중 작은 것으로 대체한다.

• 이렇게 진행하여, v가 모든 인접한 정점 w들에 대한 탐색을 끝내고 난 뒤, v의 lowlevel과 discover_time이 같을 경우 리더가 되어 현재 스택에 있는 값들을 v까지 pop 하면 된다.

코드

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

vector <vector <int>> adj;
stack <int> discover_stack;
int discover_time[10005];
int finish_time[10005];
int lowlevel[10005]; //backedge , cross edge와의 비교를 통해 어디까지 올라가는지에 대한 정보
int color_check[10005];//0->white 1->gray 2->black
int scc[10005]; //scc 그룹으로 묶기위한
int time; //discover와 finish time을 재기위한 변수
int V, E;
int scc_group = 1;

void scc_dfs(int v) {
	discover_stack.push(v);
	color_check[v] = 1;
	discover_time[v] = ++time;
	lowlevel[v] = discover_time[v];
	int size = adj[v].size();
	for (int i = 0; i < size; i++) {
		int w = adj[v][i];
		if (color_check[w] == 0) { //화이트일때 dfs 진행
			scc_dfs(w);
			lowlevel[v] = min(lowlevel[v], lowlevel[w]);
		}
		else if (color_check[w] == 1) {//backedge 일때
			lowlevel[v] = min(lowlevel[v], discover_time[w]);
		}
		else if (color_check[w] == 2) {//cross or forward
			if (discover_time[v] > finish_time[w]) { //cross
				if (scc[w]!=0) continue;
				else {
					lowlevel[v] = min(lowlevel[v], lowlevel[w]);
				}
			}
			else if (discover_time[v] < discover_time[w]) {//forward
				continue;
			}
		}
	}
	finish_time[v] = ++time;
	color_check[v] = 2;
	if (lowlevel[v] == discover_time[v]) { //리더
		while (1) {
			int idx = discover_stack.top();
			scc[idx] = scc_group;
			discover_stack.pop();
			if (idx == v) break;
		}
		scc_group++;
	}
}

int main() {
	scanf("%d%d", &V, &E);
	adj.resize(V + 1);
	for (int i = 0; i < E; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
	}
	for (int i = 1; i <= V; i++) {
		if (!color_check[i]) scc_dfs(i);
	}
	printf("%d\n", --scc_group);
	int group = 0;
	for (int i = 1; i <= V; i++) {
		if (scc[i] == -1) continue;
		group = scc[i];
		for (int j = i; j <= V; j++) {
			if (scc[j] == group) {
				printf("%d ", j);
				scc[j] = -1;
			}
		}
		printf("-1\n");
	}
	return 0;
}