SCC & BCC

알고리즘

SCC & BCC

코코딩딩 2021. 11. 6. 14:11

SCC 설명

SCC 개념 및 특징

Strongly Connected Components / 강한 연결 요소
단방향 그래프의 같은 SCC에 속한 임의의 두 정점 (u, v) 쌍에 대해서 u에서 v, v에서 u로 향하는 경로가 존재합니다.
maximal한 성질을 갖고 있어서, SCC가 가능한 커야 합니다.
예를 들어서 아래 그림에서 정점 a와 b끼리 서로를 향한 경로가 존재하지만, maximal한 성질이 있으므로 a, b, e가 SCC가 됩니다.
SCC끼리 새로운 그래프로 구축하면 DAG가 되며, 이를 통해 위상 정렬할 수 있습니다.

SCC 구현 방법

대표적으로 코사라주 알고리즘과 타잔 알고리즘이 있습니다.

Kosaraju Algorithm (코사라주 알고리즘)

DFS 두 번으로 구할 수 있으며, 역방향 그래프 활용됩니다.
간단하게 알고리즘을 설명하면 다음과 같습니다. (구현 코드는 참고자료 블로그를 참고하시면 됩니다.)
1. DFS 끝난 순서대로 스택에 정점을 저장합니다.
2. 스택 top 순서대로 방문하지 않았다면 역방향 그래프에서 DFS를 수행하고, 탐색되는 정점들을 SCC로 묶어줍니다.
시간 복잡도는 O(V+E)입니다.

Tarjan Algorithm (타잔 알고리즘)

DFS 한 번으로 구할 수 있습니다.
간단하게 알고리즘을 설명하면 다음과 같습니다.
1. DFS 탐색한 순서에 따라 정점에 번호를 매기고, 스택에 정점을 저장해줍니다.
2. 임의의 정점의 자손들이 해당 정점의 조상으로 갈 수 있는 경우가 없을 경우, 스택에서 해당 정점과 정점보다 위에 있는 정점들을 뽑아서 SCC로 묶어줍니다.
시간 복잡도는 O(V+E)입니다.

위에서 봤던 그래프를 예시로 들면 다음과 같습니다.

정점 a를 기준으로 먼저 dfs를 수행해주고 스택에 정점을 넣어주고, 첫 번째로 들어갔기 때문에 num에 1을 저장해줍니다. num이 의미하는 것은 해당 정점이 dfs를 몇 번째로 수행됐는지를 저장해주는 것이고, mn이 의미하는 것은 해당 노드를 포함한, 해당 노드에서부터 갈 수 있는 경로가 있는 노드 중 아직 SCC에 속하지 않은 정점의 num의 최솟값을 의미합니다. 그래서 어떤 SCC에 속한 정점 중 먼저 dfs를 수행한 정점의 번호를 알 수 있습니다.

아직 방문하지 않은 인접 노드를 사전 순으로 접근한다고 했을 때, 정점 b가 두 번재로 dfs를 수행함을 알 수 있습니다.

이때, 정점 b의 인접한 노드 중 방문했으며 아직 SCC에 속하지 않은 정점 a가 있으므로, 정점 b의 mn의 값은 1로 갱신이 됩니다.

이러한 방식으로 정점 h까지 dfs를 수행하면 다음과 같습니다. 이때, h는 num과 mn이 일치하게 됩니다. num과 mn이 일치한다면 해당 노드는 해당 노드의 SCC에서 제일 먼저 dfs를 수행한 노드가 됩니다. 즉, 스택에 저장된 노드 중에 해당 노드의 부모로 갈 수 있는 정점이 없음을 의미합니다.

그래서 정점 h 자체가 하나의 SCC가 되며, 스택에서 삭제해주고 dfs가 종료되게 됩니다. 또한, d의 dfs도 마치게 되는데 이때 num과 mn이 일치하지 않으므로 새로운 SCC를 생성하지 않고 그냥 종료하게 됩니다. 접근할 수 있는 부모 노드가 스택에 존재하기 때문입니다.

계속 수행해주면 다음과 같습니다. 이때, 정점 g의 num과 mn이 같으므로 정점 g가 속한 SCC에서 제일 먼저 dfs를 수행함을 알 수 있습니다. 그래서 스택에서 자기자신, 즉 정점 g가 나올 때까지 계속 빼줌으로써 정점 g가 속한 SCC를 구할 수 있습니다.

결과적으로 스택에서 f와 g가 제거되고, 두 정점이 하나의 SCC가 됩니다.

이제 마찬가지로 c의 num과 mn이 같으므로, 앞에서 했듯이 하나의 SCC를 구할 수 있습니다.

즉, 위와 같이 정점 c와 정점 d가 SCC가 됩니다. 그리고 정점 b의 인접 노드인 정점 e를 dfs를 수행시켜줍니다.

이때, 정점 a는 정점 e의 인접 노드기 때문에 정점 e의 mn은 1이 됩니다. 그리고 정점 e와 정점 b는 num과 mn이 같지 않으므로 dfs를 나오게 됩니다. 정점 a는 num과 mn이 같으므로 이전 방법과 마찬가지로 스택에서 자기 자신이 나올 때까지 제거시켜줌으로써 하나의 SCC를 만들 수 있습니다.

최종적으로, 4개의 SCC로 나눌 수 있습니다.

BCC 설명

BCC 개념 및 특징

Biconnected Component / 이중 연결 요소
무방향 그래프의 어떤 BCC 안에 속한 임의의 정점을 지워도, BCC 내의 남아있는 정점들의 연결 관계가 끊기지 않는 상태를 의미합니다.
무방향 그래프에서는 임의의 두 정점에 간선이 있다면 서로 갈 수 있는 경로가 존재하므로, 연결된 그래프 자체가 SCC가 됩니다. 그래서 다른 개념인 BCC를 적용하게 됩니다.
maximal한 성질을 갖고 있어서, BCC가 가능한 커야 합니다.
BCC 종류에는 두 가지가 있습니다.
Vertex-disjoint Biconnected Component: Articulation Point를 제거함으로써 컴포넌트를 나눕니다.
(Articulation Point: 정점을 지웠을 때 두 개 이상의 서로 연결되지 않은 그래프로 나누어지는 정점)
Edge-disjoint Biconnected Component: Bridge을 제거함으로써 컴포넌트를 나눕니다.
(Bridge: 간선이 지워지면 두 개의 서로 연결되지 않은 그래프로 나누어지는 간선)
일반적으로 BCC는 Vertex-disjoint Biconnected Component를 말합니다.

BCC 구현 방법

DFS 한 번으로 구하며, SCC 구한 방법(타잔 알고리즘)이랑 매우 유사합니다.
간단하게 알고리즘을 설명하면 다음과 같습니다. (구현 코드는 참고자료 블로그 및 문제 풀이 코드를 참고하시면 됩니다.)
1. DFS 탐색한 순서에 따라 정점에 번호를 매기고, 스택에 간선을 저장해줍니다.
2. 임의의 정점의 자손이 해당 정점의 조상으로 갈 수 있는 경우가 없을 경우, 스택에서 해당 간선과 그 간선보다 위에 있는 간선들을 뽑아서 BCC로 묶어줍니다.
시간 복잡도는 O(V+E)입니다.

SCC 문제 풀이

[백준 2150번] Strongly Connected Component (https://www.acmicpc.net/problem/2150)

2150번: Strongly Connected Component

첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정

www.acmicpc.net

방향 그래프가 주어졌을 때, SCC들로 나누는 프로그램을 작성하는 문제입니다. 타잔 알고리즘을 사용하여 다음과 같이 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 10010;

int V, E, A, B, cnt, num[MAX], chk[MAX];
vector<int> st, adj[MAX];
vector<vector<int>> ans;

int dfs(int a) {
	int mn = num[a] = ++cnt;
	st.push_back(a);
	for (int b : adj[a]) {
		if (!num[b]) mn = min(mn, dfs(b));  // 아직 방문하지 않은 경우
		else if (!chk[b]) mn = min(mn, num[b]);  // 방문했지만 어떤 SCC에 속하지 않은 경우
	}
	if (mn == num[a]) {  // 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
		vector<int> tmp;  // 해당 SCC
		while (1) {
			int b = st.back(); st.pop_back();
			tmp.push_back(b);
			chk[b] = 1;
			if (b == a) break;
		}
		sort(tmp.begin(), tmp.end()); ans.push_back(tmp);
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> V >> E; while (E--) {  // 입력
		cin >> A >> B; adj[A].push_back(B);
	}
	for (int i = 1; i <= V; ++i) {
		if (!num[i]) dfs(i);
	}
	sort(ans.begin(), ans.end());

	// 출력
	cout << ans.size() << '\n';  // SCC의 개수
	for (auto& i : ans) {  // 하나의 SCC에 속한 정점의 번호 출력
		for (int j : i)cout << j << ' ';
		cout << "-1\n";
	}
}

[백준 4013번] ATM (https://www.acmicpc.net/problem/4013)

4013번: ATM

첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차

www.acmicpc.net

SCC 단위로 위상 정렬하는 문제입니다. SCC 단위로 BFS를 해서 다음과 같이 풀었습니다.

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 500010;

int N, M, S, P, numS, cnt, ans, tm1, tm2;
int money[MAX], rs[MAX], num[MAX], chk[MAX], finalM[MAX];
map<int, int> mp;
vector<int> st, mnT, chkRs, adj[MAX];
vector<vector<int>> SCC;
queue<pair<int, int>> q;

int dfs(int a) {
	num[a] = ++cnt; int mn = cnt;
	st.push_back(a);
	for (int b : adj[a]) {
		if (!num[b]) mn = min(mn, dfs(b));
		else if (!chk[b]) mn = min(mn, num[b]);
	}
	if (mn == num[a]) {
		vector<int> tmp; int total = 0, tm = 0;
		while (1) {
			int b = st.back(); st.pop_back(); total += money[b];
			tmp.push_back(b);
			chk[b] = 1; num[b] = mn;
			if (rs[b]) tm = 1;
			if (b == a) break;
		}
		SCC.push_back(tmp);
        mnT.push_back(total);  // SCC의 총 금액 저장
        chkRs.push_back(tm);  // 레스토랑이 속한 SCC인지 저장
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M; while (M--) {  // 그래프 입력
		int a, b; cin >> a >> b; adj[a].push_back(b);
	}
	for (int i = 1; i <= N; ++i) cin >> money[i];  // 돈 액수 입력
	cin >> S >> P; while (P--) {  // 시작점과 레스토랑 입력
		int a; cin >> a; rs[a] = 1;
	}
	for (int i = 1; i <= N; ++i) {  // SCC 구하기
		if (!num[i]) dfs(i);
	}

	for (int i = 0; i < SCC.size(); ++i) mp[num[SCC[i][0]]] = i;  // 해당 num이 어느 인덱스에 저장돼 있는지 저장

	tm1 = mp[num[S]]; finalM[tm1] = mnT[tm1];  // 시작지점 설정
	q.push({ tm1,mnT[tm1]}); while (q.size()) {
    		// tm1은 현재 SCC에 해당하는 인덱스 저장, tm2는 돈 액수 저장
		tm1 = q.front().first; tm2 = q.front().second; q.pop();
		for (int i : SCC[tm1]) {
			for (int j : adj[i]) {
				if (num[i] != num[j]) {  // 같은 SCC가 아닌 경우
					int tm3 = mp[num[j]];  // j가 속한 SCC에 해당하는 인덱스 저장
					if (finalM[tm3] < (finalM[tm1] + mnT[tm3])) {  // tm1에서 tm3로 가는 게 기존의 저장된 돈보다 많을 경우
						finalM[tm3] = finalM[tm1] + mnT[tm3];  // finalM[tm3] 갱신
						q.push({ tm3,finalM[tm3] });
					}
				}
			}
		}
		if(chkRs[tm1]) ans = max(ans, tm2);  // 레스토랑인 경우, 답 갱신
	}
	cout << ans;  // 정답 출력
}

BCC 문제 풀이

[백준 11266번] 단절점 (https://www.acmicpc.net/problem/11266)

11266번: 단절점

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B

www.acmicpc.net

단절점을 찾는 문제입니다. 단절점은 속한 BCC가 두 개 이상이라는 점을 통해 다음과 같이 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PI;

int V, E, A, B, cnt, cntBCC, num[10010], chk[10010];
vector<int> ans, adj[10010];
vector<PI> st;

int dfs(int u, int v) {
	int mn = num[u] = ++cnt;
	for (int i : adj[u]) {
		if (i == v) continue;
		if (num[u] > num[i]) st.push_back({ u,i });  // 아직 방문하지 않은 간선인 경우
		if (num[i]) mn = min(mn, num[i]);  // 역방향 간선인 경우
		else {  // 트리 간선인 경우
			int tmp = dfs(i, u); mn = min(mn, tmp);
			if (tmp >= num[u]) {  // i가 u의 조상 노드로 갈 수 없는 경우, 새로운 BCC 발견됨
				++cntBCC;  // BCC의 개수 증가
				while (1) {
					// a와 b는 해당 간선의 두 정점
					int a = st.back().first, b = st.back().second; st.pop_back();
					if (chk[a] == -1);  // 단절점인 경우
					else if (!chk[a]) chk[a] = cntBCC;  // 아직 BCC에 속하지 않은 경우
					else if (chk[a] != cntBCC) {  // 다른 BCC에 속한 경우
						chk[a] = -1; ans.push_back(a);  // 단절점임을 저장해줌
					}

					// 위처럼 단절점인지, BCC에 속해 있는지에 대한 여부 확인
					if (chk[b] == -1);
					else if (!chk[b]) chk[b] = cntBCC;
					else if (chk[b] != cntBCC) {
						chk[b] = -1; ans.push_back(b);
					}

					if (a == u && b == i) break;
				}
			}
		}
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> V >> E; while (E--) {  // 그래프 입력
		cin >> A >> B; adj[A].push_back(B); adj[B].push_back(A);
	}
	for (int i = 1; i <= V; ++i) {  // BCC 분리
		if (!num[i]) dfs(i, 0);
	}
	sort(ans.begin(), ans.end());

	// 출력
	cout << ans.size() << '\n';  // 단절점 개수 출력
	for (int i : ans) cout << i << ' ';  // 단절점 출력
}

[백준 11400번] 단절선 (https://www.acmicpc.net/problem/11400)

11400번: 단절선

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A

www.acmicpc.net

단절선을 구하는 문제입니다. 자식 노드에서 도달 가능한 최소의 노드번호가 현재 노드의 번호보다 크면, 자식 이하의 정점들로부터 현재 노드 또는 그 위의 정점으로 갈 수단이 이 간선밖에 없게 되므로, 단절선이 됩니다. 이 점을 이용하여 풀면 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PI;

int V, E, A, B, cnt, cntBCC, num[100010], chk[100010];
vector<int> adj[100010];
vector<PI> st, ans;

int dfs(int u, int v) {
	int mn = num[u] = ++cnt;
	for (int i : adj[u]) {
		if (i == v) continue;
        	if (num[i]) mn = min(mn, num[i]); // 역방향 간선인 경우
		else {
			int tmp = dfs(i, u);
			if (tmp > num[u]) ans.push_back({ min(i,u),max(i,u) });  // 단절선인 경우
			mn = min(mn, tmp);
		}
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> V >> E; while (E--) {  // 그래프 입력
		cin >> A >> B; adj[A].push_back(B); adj[B].push_back(A);
	}
	for (int i = 1; i <= V; ++i) {  
		if (!num[i]) dfs(i, 0);
	}
	sort(ans.begin(), ans.end());
    
   	 // 출력
	cout << ans.size() << '\n';  // 단절선 개수
	for (auto& i : ans)cout << i.first << ' ' << i.second << '\n';  // 단절선 출력
}

[참고자료]

SCC: 코사라주 알고리즘 http://www.secmem.org/blog/2019/04/10/Graph-SCC-BCC/

타잔 알고리즘 https://m.blog.naver.com/kks227/220802519976?referrerCode=1

BCC: https://m.blog.naver.com/kks227/220802704686?referrerCode=1

https://koosaga.com/76