강결합 요소(SCC)

SCC 구현

타잔 알고리즘

// sccId, order -1로 초기화
vector<int> adj[MAX];
stack<int> st;
int sccId[MAX], order[MAX];
int vcnt, scccnt;

int dfsScc(int here) {
    int ret = order[here] = vcnt++;
    st.push(here);

    for (int there : adj[here]) {
        if (order[there] == -1) // 방문안한 정점
            ret = min(ret, dfsScc(there));
        else if (sccId[there] == -1) // 교차간선 & 아직 SCC결정 안됨
            ret = min(ret, order[there]);
    }
	// HERE에서 이전에 방문된 정점 갈 수 없음 (끊어야 함)
    if (ret == order[here]) {
        while (true) {
            int temp = st.top(); st.pop();
            sccId[temp] = scccnt;
            if (temp == here) break;
        }
        scccnt++;
    }
    return ret;
}

BCC 구할 때와 비슷하게, 각 정점이 방문할 수 있는 정점 중, 가장 방문순서가 앞서는 정점을 반환한다. 만약 그게 본인 자신이라면, SCC를 끊어야 한다. 재귀 호출이 곧 스택이기 때문에, DFS호출순서 = 스택 저장순서이다. 스택을 이용하면 재귀호출 순서 그대로 본인의 서브트리부터 본인까지 뽑아낼 수 있다. 시간 복잡도는 DFS랑 같다.

코사라주 알고리즘

// sccId, order -1로 초기화
//adj2 는 간선 방향 반대
vector<int> adj[MAX], adj2[MAX];
stack<int> st;
bool visit[MAX];
int vcnt, scccnt, sccId[MAX];

void dfs1(int here) {
    visit[here] = true;
    for (int there : adj[here]) 
        if (!visit[there]) dfs1(there);
    st.push(here);
}

void dfs2(int here) {
    visit[here] = true;
    sccId[here] = scccnt;
    for (int there : adj2[here]) 
        if (!visit[there]) dfs2(there);
}

void scc() {
	// dfs 1
	for (int i=1; i<= 정점수; ++i) 
    	if (!visit[i]) dfs1(i);
    // dfs 2
    memset(visit, false, sizeof(visit));
    while (!st.empty()) {
        int here = st.top(); st.pop();
        if (sccId[here] != -1)  continue;
        dfs2(here); scccnt++;
    }
}

원래 그래프와 간선들의 방향이 정 반대인 그래프를 하나 더 만들고, DFS를 두번한다. 두번째 dfs는 스택에 저장된 순서대로 실시하고, 한 정점에서 탐색할 수 있는 모든 정점이 같은 scc에 속한다.

• 관련 문제
  BOJ 2150

SCC와 위상정렬

DAG가 아닌 그래프에서도, SCC들 끼리는 DAG를 이룬다. 귀류법으로 쉽게 증명할 수 있는데, 서로 다른 SCC들 사이에 사이클이 존재한다면 애초에 같은 SCC에 포함됐어야 하기 때문이다. 이런 성질을 이용하면, 그래프를 SCC 단위로 압축해서 DAG로 만들 수 있다. 그러고 나면 DAG의 성질을 이용해서 문제를 쉽게 해결할 수 있는 경우가 많다.

특히 타잔 알고리즘으로 scc를 찾게 되면 scc가 저장되는 순서는 위상정렬의 역순이다. 즉 뒤에서부터 위상정렬을 이룬다. 타잔 알고리즘은 각 정점 DFS의 끝에서 SCC를 끊고 저장하기 때문인데, DFS를 통해 위상정렬을 구현하는 코드도 각 DFS의 끝에서 정점을 저장하는 것과 비슷한 흐름으로 로직이 이루어졌기 때문이다.

• BOJ 4196
  타잔으로 SCC만들고, 위상정렬 순서대로 DFS
• BOJ 3977
  마찬가지로 SCC 만들고 맨 첫 SCC에서 DFS해서 전부 탐색가능하면 첫 SCC 전체 출력, 아니면 불가능
• BOJ 4013
  SCC간의 그래프를 만들고, DAG이기 때문에 DP를 사용할 수 있다.