SCC-Kosaraju

SCC(Strongly Connected Component)

- 개념 : 방향그래프의 connected component 내 

          노드 u에서 v로 향하는 경로, 노드 v에서 u로 향하는 경로가 존재하면 해당 connected component를 SCC라 한다.

(Connected component : 그래프는 여러개의 부분 그래프로 구성될 수 있는데

 서로 연결되어 있는 여러개의 고립된 부분 그래프 각각을 connected component)

- SCC를 찾는 알고리즘

  Kosaraju's Algorithm : 2번의 DFS를 통해 SCC를 찾는다.

 과정 1. digraph G에서 임의의 정점 i부터 dfs 수행

           수행 속에서 먼저 끝나는 즉 다른 곳에 갈 곳이 없는 vertex를 stack에 push 하여 저장

i의 dfs 수행후 아직 방문하지 않은 정점이 있을 경우 해당 정점부터 다시 dfs수행

모든 정점을 방문할 때까지 dfs 수행

 과정 2. G의 간선 방향을 모두 바꾼 Gt 즉 transpose graph를 만든다.

Gt그래프를 대상으로 dfs 수행, 시작 vertex는 stack에서 pop한 순서대로 수행

스택이 비어있을 때까지 dfs 진행

이때 탐색되는 모든 정점을 SCC로 묶는다. (leader 즉 starting point가 같으면 같은 SCC)

만약 스택 top에 위치한 정점이 이미 방문한 곳이면 pop만 한다.

  코사라주 알고리즘의 시간복잡도

  과정 1. dfs 수행 시간 // O(n+m) time (인접리스트로 구현시, 만약 인접행렬이면 각 노드마다 O(n)시간 걸림)

  과정 2. Gt 만드는 시간 // O(n+m) time

dfs 수행 시간 // O(n+m) time

  ∴ O(n+m)

  코사라주 알고리즘의 공간복잡도

  인접리스트 이용시 ∴ O(n+m)

그림 예시

다음과 같은 그래프가 있을때, 방문은 항상 빠른 알파벳순으로 방문한다고 하자.

 

     과정 1) 임의의 정점 a부터 dfs를 돌려본다.

방문순서

a→b→c→d→h(→d→c)→g→f(→g→c→b)→e(→b→a)

                     (back)          (back)          (back)

stack에 쌓이는 순서(왼→오)

과정 2) transpose graph 만든다

stack의 top부터 dfs를 수행

a pop() // a→e→b

b pop() // 이미 처리한 정점이니 pass

e pop() 

c pop() // c→d

g pop() // g→f

f pop()

d pop()

h pop() // h

∴ SCC는 {a,b,e}, {c,d}, {f,g}, {h} 가 있다.

- 예시문제

[백준] 2150 Stongly Connected Component

코          https://www.acmicpc.net/problem/2150

    정답 코드)

#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
int V, E, A, B;
bool visited[10005];
vector<int> adj[10005]; //기존의 간선
vector<int> Tadj[10005]; //Transpose Graph의 간선
stack <int> st;
vector<int> scc;
vector<vector<int>> result; //SCC 저장
 
void dfs(int node) {
    visited[node] = true;
    for (int i = 0; i < adj[node].size(); i++) {
        if (visited[adj[node][i]]) continue;
        dfs(adj[node][i]);
    }
    st.push(node);
}
 
void Second_dfs(int node) {
    visited[node] = true;
    for (int i = 0; i < Tadj[node].size(); i++) {
        if (visited[Tadj[node][i]]) continue;
        Second_dfs(Tadj[node][i]);
    }
    scc.push_back(node);
}
 
int main() {
    scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++) {
        scanf("%d %d", &A, &B);
        adj[A].push_back(B);
    }
    //과정 1
    for (int i = 1; i <= V; i++) {
        if (!visited[i]) dfs(i);
    }
    //과정 2
    //Transpose Graph만들기
    for (int i = 1; i <= V; i++) {
        visited[i] = false;
        for (int j = 0; j < adj[i].size(); j++) {
            Tadj[adj[i][j]].push_back(i);
        }
    }
    while (!st.empty())
    {
        int here = st.top();
        st.pop();
 
        if (visited[here]) continue;
        Second_dfs(here);
        sort(scc.begin(), scc.end());
        result.push_back(scc);
        scc.clear();
    }
    //SCC들 오름차순으로 정렬해서 
    sort(result.begin(), result.end());
    printf("%d\n", result.size());
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            printf("%d ", result[i][j]);
        }
        printf("-1\n");
    }
    return 0;
}