개념

위상정렬 - 위키백과, 우리 모두의 백과사전

비순환 유향 그래프(Directed Acyclic Graph : DAG)의 진행 순서를 나열하는 정렬이다.

위상정렬에 사용할 두가지 변수가 필요하다.

• Indegree(전입차수) : 노드로 들어오는 간선의 수
• Outdegree(전출차수) : 노드에서 나가는 간선의 수 Outdegree는 Reverse Topological Sort에 응용한다.

구현 과정

1. indegree가 0인 모든 노드를 Queue에 넣는다.
2. 여기부터는 Queue가 빌 때까지 반복한다.
   1. 큐에서 노드를 꺼내서 출력한다. - visit
   2. 노드에서 나가는 간선을 모두 제거한다.
   3. 새롭게 indegree가 0이 된 노드들을 Queue에 넣는다.

Python

2252번: 줄 세우기

import sys
from collections import deque

I = sys.stdin.readline

v, e = map(int, I().split())

indegree = [0] * (v+1)
graph = [[] for _ in range(v+1)]

for _ in range(e):
    a, b = map(int, I().split())
    graph[a].append(b)
    indegree[b] += 1

def topological_sort():
    result = []
    q = deque()
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        cur = q.popleft()
        result.append(cur)
        for i in graph[cur]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    print(*result, sep=' ')

topological_sort()

C++

14676번: 영우는 사기꾼?

단순하게 Topological sort의 결과를 나열하는 문제가 아닌 응용문제이다. inorder를 잘 사용해야한다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m, k;
int* inorder;
int* buildings;
vector<int>* tree;
vector<pair<int, int>> log;
queue<int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> k;

    inorder = new int[n + 1];
    buildings = new int[n + 1];
    for (int i = 1; i < n + 1; i++) {
        inorder[i] = 0;
        buildings[i] = 0;
    }

    vector<int>* tree = new vector<int>[n + 1];

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        tree[a].push_back(b);
        inorder[b]++;
    }

    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        log.push_back({a, b});
    }

    int mode, num;
    bool cheet = false;
    for (auto it = log.begin(); it != log.end(); it++) {
        mode = (*it).first;
        num = (*it).second;
        // construct
        if (mode == 1) {
            // constructible?
            if (**inorder[num] == 0**) {
                // construct
                buildings[num]++;

                // unlock tech tree
                if (buildings[num] == 1) {
                    for (auto itt = tree[num].begin();
                         itt != tree[num].end(); itt++) {
                        inorder[*itt]--;
                    }
                }
            } else {
                cheet = true;
                break;
            }
        }
        // destructible?
        else {
            // unable
            if (buildings[num] == 0) {
                cheet = true;
                break;
            }
            // destroy
            else {
                buildings[num]--;

                // relock tech tree
                if (buildings[num] == 0) {
                    for (auto itt = tree[num].begin();
                         itt != tree[num].end(); itt++) {
                        inorder[*itt]++;
                    }
                }
            }
        }
    }

    if (cheet) {
        cout << "Lier!\\n";
    } else {
        cout << "King-God-Emperor\\n";
    }
}