강한 연결 요소 (Strongly Connected Component)

안녕하세요.

오늘은 줄여서 SCC 라고도 불리는 강한 연결 요소에 대해 알아보도록 하겠습니다.

사이클

유향 그래프에서 사이클을 찾는 알고리즘을 SCC 알고리즘 이라고 합니다.

하나의 SCC에 속하는 정점들은 서로에게 도달할 수 있는 것이 사이클 입니다.

{1, 2, 5} , {3, 4, 8} , {6, 7} 은 각각 서로 다른 SCC를 이루고, 그 안에서 서로 도달가능한 집합입니다.

알고리즘

SCC를 찾는 알고리즘으로 2가지가 있습니다. 둘 다 알아보도록 하겠습니다.

코사라주 알고리즘
타잔 알고리즘

코사라주 알고리즘

시간, 공간적 비용이 타잔 알고리즘보다 크다는 단점
직관적이고 이해하기 쉽다는 장점

타잔 알고리즘보다 상대적으로 구현 난이도가 낮다는 장점 또한 존재합니다.

작동 과정

모든 노드가 방문될 때 까지 순방향 그래프에서 아래 과정을 반복
1. 임의의 정점을 루트로 잡아 dfs를 수행
2. dfs가 끝나는 순서대로 stack에 노드를 담음
stack이 빌 때 까지 역방향 그래프에서 아래 과정을 반복
1. stack에서 원소를 뽑아 dfs를 수행함
2. 이 때 도달 가능한 모든 정점은 같은 scc에 속하게 됨

역방향 그래프 : 순방향 그래프에서 간선의 방향을 뒤집은 그래프

정점 1번부터 dfs를 시작하면 스택에 아래와 같이 쌓이게 됩니다.

스택에서 원소를 뽑아서 역방향 그래프에서 탐색합니다.

역방향 그래프에서 갈 수 있는 정점은 {2번, 5번} 입니다.

{1번, 2번, 5번} 은 같은 SCC 입니다.

스택에서 원소를 뽑아서 이어서 진행합니다.

2번 노드는 이미 SCC 분류가 되었으므로 패스합니다.

5번 노드 역시 마찬가지 입니다.

다음 3번 노드에서 탐색합니다.

갈 수 있는 정점은 {4번, 8번} 이므로

{3번, 4번, 8번}은 같은 SCC 입니다.

4번, 8번 노드는 이미 SCC 분류가 되었으므로 패스합니다.

7번 노드에서 갈 수 있는 정점은 {6번} 입니다.

{6번, 7번} 은 같은 SCC 입니다.

6번 노드는 이미 SCC 분류가 되었으므로 패스합니다.

스택이 비었으므로 탐색을 종료합니다.

SCC는 총 3개가 나왔습니다.

1번, 2번, 5번 노드
3번, 4번, 8번 노드
6번, 7번 노드

시간 복잡도

V : 정점 개수, E : 간선 개수 라고 둔다면,

순방향 그래프에서 시간 복잡도는 O(V + E) 입니다.

역방향 그래프에서 시간 복잡도는 O(V + E) 입니다.

각 그래프에서 모든 정점을 1번만 탐색하고, 동시에 모든 간선 또한 1번만 탐색합니다.

최종적으로 O( 2 * (V + E) ) => O(V + E) 입니다.

증명

이 알고리즘의 정당성을 증명해보겠습니다.

이를 위해선 아래 두 가지 명제를 증명하면 됩니다.

역방향 그래프에서 DFS를 돌릴 때, 정점 u에서 출발하면 u와 같은 SCC에 포함되는 모든 정점을 방문한다
스택에서 원소를 뽑아낸 정점 u는 역방향 그래프에서 DFS를 돌리면 u와 같은 SCC에 포함되지 않은 점들은 방문하지 않는다

[첫 번째 명제]

두 정점 u, v가 그래프에서 같은 SCC에 속한다면, u -> v 경로와 v -> u 경로가 존재합니다.

역방향 그래프에서도 u -> v 경로와 v -> u 경로가 존재합니다.

역방향 그래프에서 정점 u에서 출발하는 DFS는 u와 같은 SCC에 속하는 모든 정점을 방문하게 됩니다.

[두 번째 명제]

스택에서 원소를 뽑아낸 정점 : 스택에 남아있는 정점 중 순방향 그래프에서 dfs 탐색을 가장 늦게 끝낸 정점

finish_time : 순방향 그래프에서 dfs 탐색이 끝나는 시간 이라고 두겠습니다.

아래 2가지 가정을 하겠습니다.

두 가지 scc가 있다 => scc1, scc2
finish_time_1 > finish_time_2

위 가정이 맞을려면 순방향 그래프에서 두 가지 경우의 수가 있습니다.

case 1

scc_1과 scc_2 사이에 직접적인 간선이 없을 때 입니다.

scc_ancestor 에서 간선 e2를 먼저 탐색한 다음, 간선 e1을 탐색하면

finish_time_2 < finish_time_1 이라서 위의 가정에 들어 맞습니다.

(scc_2가 먼저 끝남)

만약 간선 e3가 있다고 가정하겠습니다.

(e3 : scc_2 내부의 정점 -> scc_1 내부의 정점으로 가는 간선)

그럼 scc_ancestor에서 간선 e2를 타고 dfs를 수행한 후,

간선 e3를 타고 scc_1 까지 dfs를 수행합니다.

그럼 scc_1의 dfs가 먼저 끝나고, scc_2의 dfs가 나중에 끝납니다.

(finish_time_1 < finish_time_2)

위의 가정에 들어맞지 않기 때문에 e3와 같은 간선이 없습니다.

case 2

scc_1과 scc_2 사이에 직접적인 간선이 있을 때 입니다.

간선 e4를 타고 scc_2의 정점을 다 방문하고 scc_1의 정점을 방문하기에

finish_time_1 > finish_time_2 가 맞습니다.

간선 e5가 있다고 가정해보겠습니다.

(e5 : scc_2 내부의 정점 -> scc_1 내부의 정점으로 가는 간선)

이렇게 되면 scc_1과 scc_2는 사이클이 생겨 서로 같은 scc 그룹이 됩니다.

서로 다른 scc 그룹이라는 가정에 모순됨으로 e5와 같은 간선은 없습니다.

결론

순방향 그래프에서 scc_2 내부의 정점 -> scc_1 내부의 정점 으로 가는 간선이 없다면,

역방향 그래프에서 scc_1 내부의 정점 -> scc_2 내부의 정점 으로 가는 간선 또한 없습니다.

그로인해 가장 finish_time이 큰 정점부터 탐색을 하게 되면 서로 다른 scc 그룹의 정점에 갈 일이 없기에 2번 명제도 증명이 됩니다.

코드

인접 리스트는 메모리 풀을 사용했으며,

스택과 dfs를 사용한 코드 입니다.

#include <cstdio>

const int SIZE = 2e5 + 4;
const int ESIZE = 1e6 + 4;

typedef struct NodePool {
	int cur;
	NodePool* next;
}NodePoll;
NodePoll nodePoll[ESIZE];

int pollCnt;

inline NodePool* getNode(int _cur) {
	nodePoll[pollCnt].cur = _cur;
	return &nodePoll[pollCnt++];
}

struct Vector {
	NodePoll* head;

	void push(int n) {
		NodePoll* cur = getNode(n);
		cur->next = head;
		head = cur;
	}
}adj[SIZE], rev_adj[SIZE];

struct Stack {
	int arr[SIZE];
	int top = -1;

	inline bool empty() { return top == -1; }
	inline int pop() { return arr[top--]; }
	inline void push(int n) { arr[++top] = n; }
};

inline int min(int a, int b) { return a < b ? a : b; }

struct SCC {
	Stack stack;
	bool finished[SIZE];

	void dfs(int cur) {
		finished[cur] = true;

		NodePoll* head = adj[cur].head;
		while(head) {
			int next = head->cur;
			if (!finished[next]) dfs(next);

			head = head->next;
		}

		// 탐색이 끝난 순서대로 스택에 push
		stack.push(cur);
	}

	void rev_dfs(int cur) {
		finished[cur] = false;

		NodePoll* head = rev_adj[cur].head;
		while (head) {
			int next = head->cur;
			if (finished[next]) rev_dfs(next);

			head = head->next;
		}
	}

	bool solve(int N) {
		int scc_number = 0;

		// 순방향 그래프 탐색
		for (register int i = 1; i <= N; i++) {
			if (!finished[i]) dfs(i);
		}

		// 역방향 그래프 탐색
		while (!stack.empty()) {
			int cur = stack.pop();
			if (finished[cur]) {
				++scc_number;
				rev_dfs(cur);
			}
		}

		return scc_number == 1;
	}
}scc;

int main()
{
	//freopen("input.txt", "r", stdin);

	int N, M;
	scanf("%d %d", &N, &M);

	int u, v;
	while (M--) {
		scanf("%d %d", &u, &v);
		adj[u].push(v);
		rev_adj[v].push(u);
	}

	printf("%s\n", scc.solve(N) ? "Yes" : "No");
}

타잔 알고리즘

구현이 상대적으로 복잡하다는 단점
한 번의 DFS 만을 수행해 찾을 수 있기 때문에 코사라주 알고리즘보다 빠른 성능을 가진다는 장점

단절점, 단절선 등 다른 DFS 관련 알고리즘을 풀 때 아이디어가 비슷하다는 장점도 있습니다.

과정

임의의 정점에서부터 깊이 우선 탐색을 수행해 DFS 스패닝 트리를 만듦
1. DFS 스패닝 트리 : DFS를 사용해 그래프에서 사이클이 생기지 않도록 트리로 바꾸는 것
2. 방문한 순서대로 stack에 push 함
DFS 스패닝 트리를 따라 이 간선을 자를지 여부를 결정
1. 간선을 자른다 : 다른 SCC 그룹이다
2. 현재 정점과 연결된 간선을 통해 자신의 조상 노드로 올라갈 수 있으면 간선을 자르지 않음
3. 그 외의 경우는 간선을 자름

그래프가 위와 같이 있다고 가정하겠습니다.

이를1번 정점부터 탐색해 DFS 스패닝 트리로 바꾸면 위와 같이 변합니다.

트리 간선 : DFS 스패닝 트리를 이루는 간선
역방향 간선 : 조상 노드로 가는 간선
순방향 간선 : 자손 노드로 가는 간선
교차 간선 : 그 외의 간선

루트노드부터 시작해서 트리 간선이 더 이상 없을 때 까지 탐색합니다.

1번 노드부터 탐색을 시작해 리프 노드인 6번 노드까지 도달한 과정입니다.

스택에는 DFS 방문 순서대로 쌓입니다.

6번 노드에서 갈 수 있는 정점을 확인합니다.

역방향 간선을 통해 7번 노드로 갈 수 있습니다.

자신보다 조상 노드로 갈 수 있으니 패스 합니다.

6번 노드의 dfs가 끝나서 7번 노드로 돌아온 모습입니다.

7번 노드에서 갈 수 있는 정점들 중에는 자신보다 조상 노드로 갈 수 있는 간선이 없습니다.

그럼 여기서 SCC를 만들어야 합니다.

스택에서 자신의 노드가 나올 때 까지 pop을 하고 이를 다 하나의 SCC로 추출합니다.

6번과 7번 노드는 같은 SCC에 속합니다.

8번 노드를 봤는데 역방향 간선으로 4번 노드에 갈 수 있으니 패스합니다.

4번 노드도 마찬가지로 역방향 간선을 통해 3번 노드로 갈 수 있으니 패스합니다.

3번 노드에서 자신의 조상 노드로 갈 수 있는 정점이 없습니다.

스택에서 자신의 노드가 나올 때 까지 pop을 해서 같은 scc로 묶습니다.

3, 4, 5번 노드가 같은 SCC가 됩니다.

2번 노드로 돌아왔는데 아직 트리 간선이 있습니다.

5번 노드에서 간선을 확인해보니 역방향 간선을 통해 조상 노드로 갈 수 있으므로 패스합니다.

2번 노드에서도 조상 노드로 갈 수 있습니다.

패스합니다.

1번 노드에서는 더 이상 조상 노드로 갈 수 있는 간선이 없습니다.

1번 노드가 나올 때 까지 스택에서 pop 해주고 같은 SCC로 묶어줍니다.

1번, 2번, 5번은 같은 SCC가 되었습니다.

이렇게 조상 노드로 가는지 유무는 트리 간선과 역방향 간선만 확인해주면 될 것 같습니다.

하지만, 교차 간선 또한 생각해줘야 합니다.

이렇게 DFS 스패닝 트리가 있다고 가정해보겠습니다.

여기서 5번 노드를 보면 트리 간선도 없고, 역방향 간선도 없기에 부모로 올라가는 것이 없다고 판단할 수 있습니다.

하지만 교차 간선을 통해 6번 노드 -> 7번 노드 -> 1번 노드로 올라갈 수 있으므로 패스해야 합니다.

이를 빠르게 확인할 수 있는 방법은 각 정점에 간선을 통해 올라갈 수 있는 정점을 저장해 놓으면 됩니다.

그럼 O(1) 만에 빠르게 확인할 수 있습니다.

+) 5번 -> 6번 간선을 통해 조상 노드까지 올라간다는걸 알았는데,

2번 노드에서 3번 노드로 먼저 안가고, 5번 노드로 먼저 가면 6번 노드에 대한 정보가 없으므로 모르는 것이 아닌가?

이렇게 되면 5번 -> 6번 간선이 트리 간선이 됩니다.

그래서 위의 그림과 다른 DFS 스패닝 트리가 만들어지게 될 것입니다.

달라진 DFS 스패닝 트리에서 위의 과정으로 문제를 풀면 됩니다.

시간 복잡도

O( V + E )

V : 정점의 개수

E : 간선의 개수

dfs로 모든 정점을 1번만 보면서

그와 동시에 모든 간선 또한 1번만 봅니다.

코드

dfsn 배열 : dfs 방문 순서를 기록해 놓았습니다.

dfs : 올라갈 수 있는 빠른 dfsn 넘버를 반환합니다.

#include <cstdio>

const int SIZE = 2e5 + 4;
const int ESIZE = 5e5 + 4;

typedef struct NodePool {
	int cur;
	NodePool* next;
}NodePoll;
NodePoll nodePoll[ESIZE];

int pollCnt;

inline NodePool* getNode(int _cur) {
	nodePoll[pollCnt].cur = _cur;
	return &nodePoll[pollCnt++];
}

struct Vector {
	NodePoll* head;

	void push(int n) {
		NodePoll* cur = getNode(n);
		cur->next = head;
		head = cur;
	}
}adj[SIZE];

struct Stack {
	int arr[SIZE];
	int top = -1;

	inline bool empty() { return top == -1; }
	inline int pop() { return arr[top--]; }
	inline void push(int n) { arr[++top] = n; }
};

inline int min(int a, int b) { return a < b ? a : b; }

struct SCC {
	Stack stack;
	int dfsn[SIZE], number, scc_number;
	bool finished[SIZE];

	int dfs(int cur) {
		int ret = dfsn[cur] = ++number;
		stack.push(cur);

		NodePoll* head = adj[cur].head;
		while(head) {
			int next = head->cur;

			// 방문 안한 정점 -> 트리 간선
			if (dfsn[next] == 0) ret = min(ret, dfs(next));

			// 방문 했지만 스택에서 안 나옴 -> 역방향 간선 또는 고려해야할 교차 간선
			else if (!finished[next]) ret = min(ret, dfsn[next]);

			// 스택에 담겨서 끝남 -> 고려하지 않아도 되는 교차 간선
			else;

			head = head->next;
		}

		// 자기 자신을 만날 때 까지 스택에서 정점을 추출
		if (ret == dfsn[cur]) {
			++scc_number;
			
			while (!stack.empty()) {
				int c = stack.pop();
				finished[c] = true;
				if (c == cur) break;
			}
		}

		return ret;
	}

	bool solve(int N) {
		for (register int i = 1; i <= N; i++) {
			if (dfsn[i] == 0) dfs(i);
		}

		return scc_number == 1;
	}
}scc;

int main()
{
	//freopen("input.txt", "r", stdin);

	int N, M;
	scanf("%d %d", &N, &M);

	int u, v;
	while (M--) {
		scanf("%d %d", &u, &v);
		adj[u].push(v);
	}

	printf("%s\n", scc.solve(N) ? "Yes" : "No");
}

두 알고리즘 비교

SCC 기본 문제인 https://www.acmicpc.net/problem/26146 (BOJ 26146 즉흥 여행) 이 문제를 두 알고리즘으로 풀어봤습니다.

같은 시간 복잡도 이지만,

메모리와 시간에서 차이가 꽤 나는 것을 확인할 수 있습니다.

위상 정렬과 같이 사용

DAG에서 위상 정렬이 가능하다고 배웠습니다.

하지만 SCC 알고리즘을 사용하면, 사이클이 있는 그래프에서도 위상 정렬이 가능합니다.

위의 타잔 알고리즘으로 SCC를 추출했을 때,

스택에서 빠져 나온 순서대로 SCC 번호를 매기면 아래와 같이 나옵니다.

SCC 1번 : {6번, 7번 노드}
SCC 2번 : {3번, 4번, 8번 노드}
SCC 3번 : {1번, 2번, 5번 노드}

SCC 번호를 역순으로 출력하면 위상 정렬이 됩니다.

dfs가 일찍 끝나는 scc가 먼저 번호가 매겨졌기 때문이죠.

문제

기본 문제 : https://www.acmicpc.net/problem/26146

26146번: 즉흥 여행 (Easy)

1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지만, 2번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지 않으므로, 답은 No가 된다.

www.acmicpc.net

응용 문제 : https://www.acmicpc.net/problem/26157

26157번: 즉흥 여행 (Hard)

첫째 줄에 나라의 개수 $ N $과 항공편의 개수 $ M $이 주어진다. $( 1 \le N \le 200\,000; $ $ 0 \le M \le 500\,000 )$ 둘째 줄부터 $ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 $ v $ $ w $로 주어진다. 이는 $ v $

www.acmicpc.net

풀이

https://kdr06006.tistory.com/7

[BOJ 4305] 성격 진단 테스트

백준 4305번 성격 진단 테스트 https://www.acmicpc.net/problem/4305 4305번: 성격 진단 테스트 각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알

kdr06006.tistory.com

참고 자료

코사라주 알고리즘 : https://blog.naver.com/kdr06006/222822604292

코사라주 알고리즘 증명 : https://seungkwan.tistory.com/7

타잔 알고리즘 1 : 알고리즘 문제 해결 전략 - 구종만

타잔 알고리즘 2 : https://blog.naver.com/kks227/220802519976

감사합니다.

저작자표시

'알고리즘 & 자료구조' 카테고리의 다른 글

LIS (Longest Increasing Sequence) (0)	2023.08.02
2-SAT (0)	2023.07.24
최소 스패닝 트리 (Minimun Spanning Tree) (0)	2023.07.14
A* algorithm (0)	2023.07.07
Topological Sort (위상 정렬) (0)	2023.06.29

Computer Programming

강한 연결 요소 (Strongly Connected Component)

사이클