Strongly Connected Component [c++]

 SSC(강한결합요소)는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있다. 즉 사이클이 발생할 경우

무조건 SCC에 속한다. 이는 Directed Graph에서만 의미가 있는데, Undirected Graph는 그래프 전체가 무조건 SCC이기 때문이다.

 SCC를 추출하는 알고리즘에는  코사라주 알고리즘과 타잔 알고리즘이 있는데 코사라주 알고리즘이 구현은 쉽지만 타잔 알고리즘이 더 적용하기 좋다는 점에서 타잔 알고리즘을 사용하여 구현 할 것이다.

 

1. dfs를 할 때, 처음 정점 x의 부모에게 고유한 번호인 id를 부여한다. 예를들어 d[x] = ++id; 로 작성하면

x의 부모인 d[x]에게 현재 id값에 1을 더한 번호를 부여하는 것이다. 즉 부모==id값이라고 생각하면 됨

2. 정점 x를 stack에 push 한다.

3. x의 자식 노드들인 y에 대해,  d[y] == 0 이면 y는 id를 부여받지 못한 것이므로 아직 방문하지 않은것이다.

한 사이클 내에서는 고유번호가 낮은 것이 parent이다. 그래서 parent = min(parent, d[y])를 통해 누가 부모인지 확인한다.

4. d[y]가 0이아니고(id를 부여 받았고 == 방문을 했고)사이클 찾기가 완료되었는지 확인하는 변수인 finished가 fasle이면 아직 하나의 사이클 집단을 확인하는 과정이므로

parent = min(parent, d[y])를 통해 누가 부모인지 가려낸다.

5. 위 과정을 통해 정상적으로 사이클을 확인 했다면 parent == d[x] 가 될 것이므로(부모 노드가 자기 자신이 될 것 이므로) vector<int> scc라는 소규모 집합 벡터를 만든후 stack에서 하나씩 pop하면서 이를 scc.push_back 해준다. 그리고

사이클 안에 속하는 정점들의 finish 값을  true로 만들어 준다. 이 과정을 정점 x가 pop 될 때까지 반복한다.

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 10001

using namespace std;

int id, d[MAX]; // 각 노드마다의 고유 번호
bool finished[MAX]; // 특정한 노드가 DFS가 끝났는지 확인
vector<int> a[MAX]; // 열max, 행은 가변의 벡터 생성
vector<vector<int>> SCC;
stack<int> s;

// dfs는 총 점점의 갯수만큼 실행

 

int dfs(int x) {
d[x] = ++id; // 노드마다 고유한 번호 할당  ★ 부모의 고유 번호를 부여해 주는것임
s.push(x); // 스택에 자기 자신을 삽입

int parent = d[x]; // x의 부모
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (d[y] == 0) { //  y의 고유 번호, 즉 부모를 아직 방문하지 않았다면
parent = min(parent, dfs(y));
}
else if (!finished[y]) { // 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; // 자신의 부모 값을 반환
}

 

int main() {
int v = 11; // 정점의 개수

a[1].push_back(2);
a[2].push_back(3);
a[3].push_back(1);
a[4].push_back(2);
a[4].push_back(5);
a[5].push_back(7);
a[6].push_back(5);
a[7].push_back(6);
a[8].push_back(5);
a[8].push_back(9);
a[9].push_back(10);
a[10].push_back(11);
a[11].push_back(3);
a[11].push_back(8);

for (int i = 1; i <= v; i++) {
if (d[i] == 0) dfs(i);
}
cout << "SCC의 갯수 : " << SCC.size() << endl;
for (int i = 0; i < SCC.size(); i++) {
cout << i + 1 << "번째 SCC : " << ' ';
for (int j = 0; j < SCC[i].size(); j++) {
cout << SCC[i][j] << ' ';
}
cout << endl;
}


return 0;
}