정의

하나의 연결된 컴포넌트
어느 두 정점을 선택하더라도 경로가 있고 반대의 경로도 있다.

특징

SCC를 묶어서 그룹으로 표현하면 DAG가 형성된다.
(당연히 양방향이 있으면 그것은 SCC 그룹으로 묶였을 것이다.)

알고리즘은 코사라주 알고리즘, 타잔 알고리즘이 있다.

타잔 알고리즘

SCC가 DFS 스패닝 트리에서 서브트리를 이룬다는 기본적인 아이디어에서 나왔다.

절단점과 다르게 visited 인 정점에서만 dfs_low(u)를 갱신한다.
스패닝 트리에서 dfs_low(u) == dfs_num(u) 이면, u가 하나의 SCC 시작 정점이 된다.

소스 코드

vi dfs_num, dfs_low, visited;
    
void tarjanSCC(int u){
    dfs_low[u] = dfs_num[u] = dfsNumberCount++;
    S.push_back(u) // u를 방문 순서에 따라 배열에 저장.  
    visited[u] = 1;
    for (int j = 0; j < AdjList[u].size(); ++j){
        int v = AdjList[u][j];
        if (dfs_num[v] == UNVISITED)
            tarjanSCC(v);
        if (visited[v])
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
    }
    
    if (dfs_low[u] == dfs_num[u]){ // SCC 루트를 구했으니 하나씩 꺼냄
        while(1){
            int v = S.back(); S.pop_back();
            visited[v] = 0;
            if (u == v) break;
        }
    }
}

코사라주 알고리즘

그래프 G와 전치 그래프 G’를 이용한다.
전치 그래프 G’는 그래프 G의 간선을 거꾸로 된 방향으로 바꾼 것이다. (u->v) => (v->u)
G와 G’는 서로 같은 SCC를 가진다. (SCC정의 대로 서로 도달하는 부분은 방향을 바꿔도 서로 도달하기 때문)

동작 방식

  1. 각 정점 u에 대해 종료 시간 u.f를 계산 (dfs(G) 호출)
  2. 전치 그래프 G’를 생성
  3. DFS(G’)를 호출한다. 호출할 때, u.f가 감소하는 순서(늦게 끝난 정점부터)로 호출한다.
  4. 3에서 깊이 우선 포레스트를 만드는데(SCC가 DAG를 이루는 데 역순으로 호출하면 각 SCC하나씩 생성됨) 그것을 출력한다.