[알고리즘] 강한 연결 요소(Strongly Connected Component, SCC) 알아보기

강한 연결 요소

그래프에서 강하게 연결 되어있는 집합이다.

같은 SCC집합에 속해있는 정점끼리는 도달가능하다는 특징을 가지고 있다.

집합내 모든 두 점이 서로 도달 가능할때 강하게 연결 되어있다고 한다.

 

위의 그림과 같은 그래프로 설명을 할 것 이다.

위의 그래프에서의 SCC는 다음 그림과 같은 집합으로 나타낼 수 있다.

 

같은 집합내의 원소들은 서로 도달가능하다.

예를들어 2와 4 를 보면 2는 4로 도달이 가능하지만 4는 2로 도달할 수 없기 때문에 2, 4는 같은 SCC가 아니다.

반면에, {1,2,3} 을 보면 1에서 2, 1에서 3 / 2에서 1 ,2에서 3/ 3에서 1, 3에서 2 어떤 두 정점을 잡아도 해당 노드로 이동이 가능하기 때문에 같은 SCC에 속한다고 보면 된다.

 

이제 SCC의 원소를 찾아내는 알고리즘을 설명하겠다.

SCC의 대표적인 알고리즘은 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다.

코사라주 알고리즘은 구현이 쉽지만, 타잔 알고리즘이 적용이 쉬운점에서 타잔 알고리즘을 설명하겠다.

타잔 알고리즘은 모든 노드에서 DFS를 수행하여 SCC를 찾는 알고리즘이다.

 

설명

 

🐘성립조건 : 다음과 같이 한 노드가 다시 자기자신에게 돌아올 수 있어야 SCC가 성립된다.

먼저 1번 노드부터 DFS 수행을 시작한다.

시작하고 1번 노드의 고유id와 SCC 집합내의 부모값을 설정한다. 그후에 스택에 담아준다.

 

그후 2번 노드도 id와 부모값을 설정해주고, 스택에 담아준다.

여기서 2번 노드의 부모가 2인 이유는 아직 SCC가 형성 되지 않았기 때문에

2번 노드는 자기자신의 고유id인 2를 부모값으로 갖는다.

DFS가 아직 3번째 노드를 수행하고 있으므로 아직은 3번째 노드의  id 와 부모가 3이다.

3번째 노드의 DFS가 수행중에 DFS가 진행중인 1번째 노드를 만났다. 

DFS가 진행중인 노드를 만났다는 뜻은 곧 SCC가 형성 되었다는 뜻이다.

그러므로 3번노드에서 더이상 DFS를 수행하지 않고, 만난 노드의 id만 가져와 부모노드에 저장한다.

3번째 노드의 DFS가 끝난후 2번째 노드의 DFS로 돌아간 후 2번째 노드의 부모값도 1로 변경 되었다.

2번째 노드의 DFS가 끝난후 1번째 노드의 DFS에서 id와 부모값이 일치한다.

SCC의 부모 노드로 다시 돌아왔으므로(SCC 집합 확정) 스택에서 자기 자신이 나올 때까지 뽑는다.

다음은 4번째 노드에서 DFS가 시작되어 DFS를 노드9 까지 수행한 결과이다.

id: 7의 부모값이 5인 이유는 DFS 수행이 더 낮은 노드부터 수행이 되기 때문에 8번 노드보다 5번노드를 먼저 방문해

부모값이 5로 먼저 업데이트 되었다.

 

다음 수행에서 노드 9의 부모값이 8로 업데이트 되고, 다시 노드8로 돌아가 id와 부모값이 같으므로

SCC가 확정 되고, 스택에서 추출한다.

이렇게 SCC추출이 마무리가 된다.

구현

#include <iostream>
#include <vector>
#include <stack>

#define MAX 10001

using namespace std;

int id, d[MAX];
bool finished[MAX];
vector<int> edge[MAX];
vector<vector<int>> SCC;
stack<int> s;

int dfs(int x) {

	d[x] = ++id;
	s.push(x);

	int parent = d[x];

	for (int i = 0; i < edge[x].size(); i++) {
		int y = edge[x][i];
		if (d[y] == 0) parent = min(parent, dfs(y));
		else if (!finished[y]) parent = min(parent, d[y]);
	}
	
	if (parent == d[x]) {
		vector<int> scc;

		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			if (t == x) break;
		}
		SCC.push_back(scc);
	}

	return parent;
}

🐘추천 문제🐘

백준 2150번

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component