SCC?

Strong Connected Component
방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC라 칭한다.

글로만 봐서는 무슨 소린지 잘 모르겠다 위의 그림을 보자
예를 들어 1과 3을 잡아보면
1에서 3으로 가는 경로가 존재하고 3에서 1로 가는 경로도 존재한다.
그러므로 1과 3은 하나의 SCC다.

그럼 1과 4는 어떨까? 4에서 1로 가는 경로는 있지만 1에서 4로 가는 경로는 존재하지 않는다.
그러므로 1과 4는 하나의 SCC가 될 수 없는 것이다.

위 조건들을 만족하는 SCC그룹으로 묶으면 위의 그림에서는 3개의 SCC가 나온다.

그리고 SCC는 방향그래프에서 의미가 있다.
무방향 그래프에서 SCC를 따지는건 의미가 없다.

SCC 어떻게 찾을까?

SCC를 찾는 알고리즘은 2개가 존재한다.
코사라주 알고리즘과 타잔 알고리즘이다.
개념은 코사라주 알고리즘이 더 쉽고 구현도 코사라주가 더 쉽다.
하지만 DFS 한번으로 구할 수 있고 적용하는데 더 좋기 때문에 타잔 알고리즘이 더 많이 쓰인다.
시간복잡도는 두 알고리즘 모두 O(V+E)이다.

코사라주 알고리즘

DFS 탐색을 두번하여 SCC를 구하는 알고리즘이다.
순서에 따라 어떻게 돌아가는지 보자

1. DFS 탐색을 시작하며 탐색이 끝난 순서로 스택에 삽입

DFS를 돌며 방문한 순서가 아닌 탐색이 끝나 DFS를 나가는 순서대로 스택에 삽입한다.

2. 역방향 그래프를 만들고 DFS 탐색

원래 입력받은 방향의 반대인 역방향 그래프를 하나 만든다.
그리고 스택의 top에서부터 원소를 하나씩 꺼내어 DFS를 탐색한다.

3. DFS 탐색 단위로 SCC 구별

1에서부터 DFS를 탐색하면 1, 2, 3을 방문한다.
그럼 1, 2, 3은 하나의 SCC로 판별한다.
2는 이미 방문했으므로 그냥 pop한다.

4. DFS 탐색 단위로 SCC 구별

4에서 DFS를 탐색하면 4자신밖에 갈 수 없다.
그러므로 4혼자 SCC이다.

5. DFS 탐색 단위로 SCC 구별

5에서 DFS를 탐색하면 5, 6, 7을 방문한다.
5, 6, 7은 하나의 SCC이다.
이미 방문한 점들을 pop해주고 스택이 비면 탐색이 끝난다.

코사라주 알고리즘 코드

코드는 백준 2150번 - Strongly Connected Component을 기준으로 작성했다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int v, e, cnt, visited[10001]; // visited - 방문 확인 배열
vector<vector<int>>scc; // scc 결과를 저장할 벡터
vector<vector<int>>arr, rarr; // 그래프와 역방향 그래프
stack<int>st;
bool cmp(vector<int> x, vector<int> y) {
	return x[0] < y[0];
}

void dfs(int now) { // 스택에 넣는 DFS
	visited[now] = 1;
	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];
		if (!visited[next])
			dfs(next);
	}
	st.push(now);
}

void dfs2(int now, int v) { // SCC를 판별하는 DFS
	visited[now] = 1;
	scc[v].push_back(now);
	for (int i = 0; i < rarr[now].size(); i++) {
		int next = rarr[now][i];
		if (!visited[next])
			dfs2(next, v);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> v >> e;
	arr.resize(v + 1);
	rarr.resize(v + 1);
	for (int i = 0; i < e; i++) {
		int a, b; cin >> a >> b;
		arr[a].push_back(b); // 정방향 그래프
		rarr[b].push_back(a); // 역방향 그래프
	}
	
	for (int i = 1; i <= v; i++) {
		if (!visited[i])
			dfs(i); // 방문하지 않은 점들을 DFS 돌며 스택에 값 추가
	}
	fill(visited, visited + 10001, 0); // 방문배열 초기화
	while (!st.empty()) { // 스택이 빌 때까지 SCC 판별
		int now = st.top();
		st.pop();
		if (visited[now])
			continue;
		scc.resize(++cnt); // cnt는 SCC들을 구분하기 위해 만든 것
		dfs2(now, cnt - 1);
	}
	for (int i = 0; i < cnt; i++)
		sort(scc[i].begin(), scc[i].end()); // 각 SCC안에 노드들을 정렬
	sort(scc.begin(), scc.end(), cmp); // SCC 전체 정렬 cmp만들어야 함
	cout << cnt << "\n";
	for (int i = 0; i < cnt; i++) {
		for (int j = 0; j < scc[i].size(); j++)
			cout << scc[i][j] << " ";
		cout << -1 << "\n";
	}
	return 0;
}

타잔 알고리즘

DFS 탐색 한번으로 SCC를 구하는 알고리즘이다.
단절점 알고리즘 에 들어가는 개념이 다시 나온다.
순서에 따라 어떻게 돌아가는지 보자

1. DFS 탐색을 시작하며 탐색 순서대로 스택에 삽입

코사라주와 달리 DFS를 방문한 순서대로 스택에 삽입한다.
부모라는 개념이 있는데 단절점 알고리즘에서 리턴해주는 최소값과 같다고 생각하면 된다.
부모의 초기값은 자기 자신의 번호이다.

2. 3번 노드의 최종 부모인 1을 반환

3번에서 자신의 부모인 1을 만나게 된다.
3은 자신의 부모값을 1로 갱신하고 1을 반환한다.

3. 2번 노드가 1을 받아 부모값 갱신

2번 노드는 3번으로부터 부모값 1을 리턴받는다.
그리고 자신의 현재 부모인 2와 비교해서 더 작은 1을 부모값으로 갱신한다.

4. 2번 노드에서 4번 노드로 탐색 시작

7번까지 탐색을 끝내고 부모값도 채워넣는다.

5. 7번 노드에서 부모인 5번을 반환

7번 노드에서 자신의 부모인 5번을 만난다.
7번은 부모값을 5로 갱신하고 5를 리턴한다.

6. 6번 노드가 5를 받아 부모값 갱신

6번 노드는 7번으로부터 부모값 5을 리턴받는다.
그리고 자신의 현재 부모인 6와 비교해서 더 작은 5을 부모값으로 갱신한다.

7. 자신과 동일한 값 받아 스택에서 pop 시켜줌

5번 노드는 자신과 동일한 부모값인 5를 6으로부터 받는다.
그럼 스택에서 5가 나올때까지 pop을 해준다.
이 때 5를 포함한 스택에서 pop되는 노드들이 같은 SCC에 속하게 된다.

8. 4번 노드가 5번으로부터 5를 받는다.

4번 노드는 5번으로부터 부모값으로 5를 받지만
자신이 가지고있는 4보다 크므로 값을 갱신하지 않는다.
4번 노드는 자신의 부모값이 자신과 같으므로
스택에서 4가 나올때까지 pop한다.
4하나만 스택에서 빠진다. 그러므로 4 혼자 SCC이다.

9. 2번 노드가 4번으로부터 4를 받는다.

2번 노드는 4번으로부터 부모값 4를 받지만
자신이 가지고있는 1보다 크므로 값을 갱신하지 않는다.

1번 노드로 리턴하고 1번은 자신의 부모값과 동일한 1을 받는다.
스택에서 1번이 나올때까지 pop한다.
1을 포함한 1, 2, 3이 같은 SCC에 속한다.

타잔 알고리즘 코드

코드는 백준 2150번 - Strongly Connected Component을 기준으로 작성했다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int v, e, cnt, res_size, discover[10001], scc[10001];
// discover - DFS 탐색 순서, scc - SCC 저장 배열
vector<vector<int>>res; // SCC 결과 저장 벡터
vector<vector<int>>arr; // 그래프
stack<int>st;
bool cmp(vector<int> x, vector<int> y) {
	return x[0] < y[0];
}

int dfs(int now) {
	st.push(now);
	discover[now] = cnt++; // 몇번째로 탐색됐는지 저장
	int parent = discover[now]; // 부모를 자기 자신의 번호로 초기화
	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];
		if (discover[next] == -1) // 아직 탐색하지 않았다면 DFS탐색
			parent = min(parent, dfs(next));
		else if (scc[next] == -1) // 이미 탐색했고 scc로 확정되지 않았다면
			parent = min(parent, discover[next]); // 더 작은 부모값이 있다면 갱신
	}
	if (parent == discover[now]) { // 부모와 자기 자신의 번호가 같다면
		vector<int>tmp;
		while (true) { // 자기 자신이 나올때까지 pop
			int here = st.top();
			st.pop();
			scc[here] = res_size;
			tmp.push_back(here);
			if (here == now)
				break;
		}
		sort(tmp.begin(), tmp.end());
		res.push_back(tmp);
		res_size++;
	}
	return parent;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> v >> e;
	arr.resize(v + 1);
	for (int i = 0; i < e; i++) {
		int a, b; cin >> a >> b;
		arr[a].push_back(b);
	}

	fill(discover, discover + 10001, -1);
	fill(scc, scc + 10001, -1);
	for (int i = 1; i <= v; i++) {
		if (discover[i] == -1)
			dfs(i);
	}
	sort(res.begin(), res.end(), cmp);
	cout << res_size << "\n";
	for (int i = 0; i < res_size; i++) {
		for (int j = 0; j < res[i].size(); j++)
			cout << res[i][j] << " ";
		cout << -1 << "\n";
	}
	return 0;
}

SCC 알고리즘

SCC?

SCC 어떻게 찾을까?