[웰노운] Tarjan's algorithm

서론

Tarjan’s algorithm에 대해 알아보자.

SCC를 구하는 알고리즘은 많지만 크게 두 가지가 존재한다.

1. Kosaraju’s algorithm
2. Tarjan’s algorithm

코사라주 알고리즘은 타잔에 비하면 이해도 쉽고, 구현도 쉬운 편이다.

허나 역방향 그래프 $G^r$과 그래프의 순회를 수행한 정보를 저장할 스택 1 ~ 2개 정도의 추가적인 공간이 요구된다는 점.

타잔 알고리즘이 응용할 수 있는 가능성과 DFS에 대한 이해도를 올려주기에, 이번 기회에 배워보려고 한다.

Kosaraju’s algorithm

코사라주의 방식을 간단히 알아보자면,

역방향 그래프를 DFS 순회하여 post-visit 순회하여 얻은 순서를 역순으로 DFS하면,

이 DFS에서 순회한 모든 노드들은 SCC를 이룬다는 것이다.

본론

아이디어

반면, 타잔의 방식은 살펴보면, 단순히 DFS를 응용해서 SCC를 구하는 것이다.

DFS를 수행해 각 노드의 previsit[i]를 구하고,

추가적으로 low[i]: i번 정점이 도달할 수 있는 최소의 previsit[i] 값으로 정의할 수 있다.

만약 low[i] == previsit[i]이라면, 우리는 i번 노드가 SCC의 루트임을 알 수 있다. (증명 스킵)

SCC를 구하기

그렇다면 위 아이디어를 이용해 SCC를 구하는 알고리즘을 설계하자.

우리는 가능한 DFS 하나로 이를 수행하여 보자.

DFS를 수행하면서 pre[i], low[i]를 구한다.

이 과정에서 추가로 스택에 노드 i를 push하고, 다음 노드를 DFS를 수행한다.

postvisit에서 만약 low[i] == previsit[i]이라면,

현재 우리가 얻은 스택은 i번째의 노드의 자손들이 전부 들어가있다.

따라서 스택에서 v가 나올 때까지 pop을 진행해주면 되고, 여기서 pop된 원소들은 하나의 SCC를 이룬다.

정리하면, 이렇다.

1. previsit에서는 단순히 pre[i], low[i] 초기화
2. 이후 edge의 방문 여부에 따라 DFS 전파 처리.
3. 만약 방문하지 않은 노드라면, low[v] = min(low[v], low[u])로 갱신
4. 방문한 노드이고 SCC로 확정이 되지 않은 노드라면, low[v] = min(low[v], pre[u])로 갱신
5. postvisit에서 low[i] == previsit[i]이라면 스택에서 i가 나올 때까지 pop
6. 위 과정에서 얻은 노드들은 SCC.

의사 코드

위 내용을 구현한 c++ 코드이다.

배열은 0으로 초기화 되어있다고 전제한 코드이다.

int pre[10001], low[10001], t = 1, scc[10001];
stack<int> st;
void tarjan(int cur) {
    pre[cur] = low[cur] = t++;
    st.push(cur);

    for (auto &&nxt : adj[cur]) {
        if (pre[nxt] == 0) {
            tarjan(nxt);
            low[cur] = min(low[cur], low[nxt]);
        } else if (scc[nxt] == 0) {
            low[cur] = min(low[cur], pre[nxt]);
        }
    }

    if (pre[cur] == low[cur]) {
        while (st.top() != cur) {
            scc[st.top()] = cur;
            st.pop();
        }
        scc[st.top()] = cur;
        st.pop();
    }
}