위의 그래프에서 1-4-5는 서로 도달은 가능하지만 외부에서는 도달할 수 없는 형태를 가지고 있다!
위와 같이 1-4-5, 2-3-7, 6과 같은 집합을 SCC라고 할 수 있다.
특징!
SCC는 내부의 노드들은 서로 이동할 수 있는 경로가 존재해야 한다.
SCC를 압축한다면 DAG가 된다. (DAG: Directed Acyclic Graph(비순환 그래프))
알고리즘!
SCC를 찾는 알고리즘은 Kosaraju 알고리즘과 Tarjan 알고리즘이 있다.
Kosaraju Algorithm
과정 1. DFS를 실행 -그래프에서 DFS를 수행하며 종료 순서대로 정점을 스택에 저장해 준다!
2. 그래프를 반대로 뒤집기 -스택에 넣은 정점들을 꺼내가면서 반대로 dfs 탐색을 시작해 준다.
최종 코드(BOJ 2150)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v[100004], rev_v[100004];
stack<int> stk;
vector<bool> visited(100004);
vector<vector<int>> SCC;
void dfs(int x) {
visited[x] = 1;
for (auto i : v[x]) {
if (!visited[i]) dfs(i);
}
stk.push(x);
}
void rev_dfs(int x, vector<int>& com) {
visited[x] = 1;
com.push_back(x);
for (auto i : rev_v[x]) {
if (!visited[i]) rev_dfs(i, com);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
rev_v[y].push_back(x);
}
fill(visited.begin(), visited.end(), 0);
for (int i = 1; i <= n; i++) {
if (!visited[i]) dfs(i);
}
fill(visited.begin(), visited.end(), 0);
while (!stk.empty()) {
int x = stk.top();
stk.pop();
if (!visited[x]) {
vector<int> com;
rev_dfs(x, com);
sort(com.begin(), com.end());
SCC.push_back(com);
}
}
sort(SCC.begin(), SCC.end());
cout << SCC.size() << '\n';
for (auto i : SCC) {
for (auto x : i) cout << x << ' ';
cout << "-1\n";
}
}
dfs 탐색
void dfs(int x) {
visited[x] = 1;
for (auto i : v[x]) {
if (!visited[i]) dfs(i);
}
stk.push(x);
}
-dfs탐색을 수행해 주는데 수행이 종료되었을 때 정점을 스택에 넣어준다.
역 방향 탐색
void rev_dfs(int x, vector<int> &component) {
visited[x] = 1;
component.push_back(x);
for (auto i : rev_v[x]) {
if (!visited[i]) rev_dfs(i, component);
}
}
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (!visited[node]) {
vector<int> component;
rev_dfs(node, component);
sort(component.begin(), component.end());
SCC.push_back(component);
}
}
-스택의 top()부터 탐색(역방향 탐색)을 하면서 SCC를 찾아준다. -만약 정점이 방문되지 않았다면 그 정점부터 시작하여서 방문을 해주고 dfs방문을 하면서 방문한 정점은 com 백터에 넣어둔다.
Tarjan Algorithm
과정 1. DFS탐색을 하면서 탐색 순서와 고유 번호를 지정해 준다. -한 배열에는 dfs탐색의 순서를 지정해 주고 또 다른 배열에는 최소 방문 번호를 지정해 준다.
2. 역방향 간건을 이용해서 최소 방문 번호를 갱신해 준다. -만약 SCC가 발견된다면 그 내부에 있는 모든 정점의 최소 방문 번호를 SCC내부에서 가장 작은 번호로 변경해 준다!
3. 스택에서 저장되어 있는 값들을 꺼내서 SCC를 구한다! -SCC의 정점들은 모두 방문처리를 해준다.
최종 코드(BOJ 2150)
#include <bits/stdc++.h>
using namespace std;
int n, m, id;
vector<int> adj[100004], SCC[100004];
int d[100004], low[100004], sccIndex;
bool finished[100004];
stack<int> stk;
void dfs(int x) {
d[x] = low[x] = ++id;
stk.push(x);
for (int next : adj[x]) {
if (d[next] == 0) {
dfs(next);
low[x] = min(low[x], low[next]);
}
else if (!finished[next]) {
low[x] = min(low[x], d[next]);
}
}
if (low[x] == d[x]) {
vector<int> scc;
while (true) {
int node = stk.top();
stk.pop();
scc.push_back(node);
finished[node] = true;
if (node == x) break;
}
sort(scc.begin(), scc.end());
SCC[sccIndex++] = scc;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if (d[i] == 0) dfs(i);
}
cout << sccIndex << '\n';
sort(SCC, SCC + sccIndex);
for (int i = 0; i < sccIndex; i++) {
for (int x : SCC[i]) cout << x << " ";
cout << "-1\n";
}
}
주요 변수들
vector<int> adj[100004], SCC[100004];
int d[100004], low[100004], sccIndex; //d: 방문 순서, low: 최소 방문 순서, sccIndex: scc개수
bool finished[100004]; //finished: 이미 SCC그룹화 된 정점은 방문처리
stack<int> stk; //정점들을 역방향으로 탐색
-low 같은 경우는 처음에는 d와 동일하게 방문 순서를 처리해 주다가 SCC가 발견된다면 SCC 내에서 제일 작은 방문순서로 모든 정점을 업데이트해준다.
dfs 탐색
void dfs(int x) {
d[x] = low[x] = ++id;//방문 순서를 저장해줌 d,low동일
stk.push(x); //현제 방문 정점은 스택에 넣어줌
for (int next : adj[x]) {
if (d[next] == 0) { //방문 처리 안되어 있다면 다음 정점을 탐색해줌
dfs(next);
low[x] = min(low[x], low[next]); //방문을 완료한 이후에는 low값을 업데이트
}
else if (!finished[next]) { //SCC그룹화 하지 않았다면 low업데이트
low[x] = min(low[x], d[next]);
}
}
if (low[x] == d[x]) { //low[x]==d[x]: 이미 방문하였고 SCC그룹화 안된 점을 발견한 경우!
vector<int> scc;
while (true) {
int node = stk.top();
stk.pop();
scc.push_back(node);
finished[node] = true; //SCC그룹화 한 경우 방문 처리해주기!
if (node == x) break; //만약 현제 노드, 즉 SCC그룹 까지 SCC처리 해주었으면 종료
}
sort(scc.begin(), scc.end());
SCC[sccIndex++] = scc;
}
}
-low는 다음 정점을 방문을 마친다음에 low를 업데이트하거나 SCC를 그룹화한 다음에 low를 업데이트해준다.
-low[x]==d[x] 의 경우는 이미 방문을 했다는 의미와 가장 작은 방문 순서라는 의미이다!
BOJ 2150번의 문제를 예제로 예시를 들어서 low의 양상을 보면 다음과 같다. BOJ 2150
