위상 정렬

그래프의 위상 정렬 문제는 다음과 같습니다. 방향 그래프가 주어졌을 때, 그래프의 모든 간선이 앞선 정점에서 나중 정점으로 향하도록 하는 정점의 순서를 찾아야 합니다.

이는 예를 들어 서로 연관된 작업들의 수행 순서를 계획할 때 유용할 수 있습니다. 옷을 입어야 하는데, 올바른 순서로 반바지(1), 바지(2), 부츠(3)를 입고, 힙스터처럼 바지를 접어 올린 다음(4), 신발 끈을 묶어야(5) 합니다.

첫째로, 사이클이 있는 그래프는 위상 정렬할 수 없다는 점을 바로 짚고 넘어가겠습니다. 사이클을 배열에 어떻게 배치하더라도 사이클의 간선을 따라 계속 오른쪽으로만 이동할 수는 없기 때문입니다.

둘째로, 그 역도 성립합니다. 사이클이 없다면 그 그래프는 반드시 위상 정렬할 수 있습니다. 어떻게 하는지 지금 보이겠습니다.

나가는 간선이 하나도 없는 정점은 항상 마지막에 놓을 수 있으며, 비순환 그래프에는 이러한 정점이 반드시 존재합니다(그렇지 않다면 역방향 간선을 따라 무한히 이동할 수 있을 것입니다). 이로부터 곧바로 구성적 증명이 도출됩니다. 나가는 간선이 없는 정점을 반복적으로 배열에 넣고 그래프에서 제거합시다. 이 과정을 마친 후에는 배열을 뒤집어야 합니다.

이 알고리즘은 dfs에서 정점을 빠져나오는 시각에 주목하면 더 간단하게 구현할 수 있습니다. 가장 먼저 빠져나오게 되는 정점은 새로운 나가는 간선이 없는 정점입니다. 그다음부터는 나가는 간선이 있더라도 그 간선이 모두 이미 빠져나온 정점으로만 향하는 정점에서만 빠져나오게 됩니다.

따라서 정점들을 dfs에서 빠져나오는 순서대로 적은 다음, 얻은 목록을 뒤집기만 하면 올바른 위상 정렬 중 하나를 얻게 됩니다.

const int maxn = 1e5;

bool used[maxn];
vector<int> t;

void dfs(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
    t.push_back(v);
}

void topological_sort() {
    for (int v = 0; v < n; v++)
        if (!used[v])
            dfs(v);
    reverse(t.begin(), t.end());
}

위상 정렬은 결과 배열에서 정점의 번호를 비교하여 도달 가능성을 확인하는 데 사용할 수 있습니다. 정점 $a$가 정점 $b$보다 뒤에 온다는 사실은 $a$에서 $b$로 도달할 수 없음을 의미합니다. 그러나 $b$에서 $a$로는 도달할 수도 있고 도달할 수 없을 수도 있습니다.