Topological Sort (위상 정렬)

코드

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

vector<int> adj[1001];
int in[1001], ans[1001];

int main()
{
    int n, m, i, j, k, l;
    queue<int> q;

    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d", &k);
        for (i = 0; i < k; i++) {
            scanf("%d", &l);
            if (i >= 1) {
                adj[j].push_back(l);
                in[l]++;
            }
            j = l;
        }
    }

    for (i = 1; i <= n; i++)
        if (in[i] == 0)
            q.push(i);

    for (i = 0; i < n; i++) {
        if (q.empty()) {
            printf("0");
            return 0;
        }

        int v = q.front();
        q.pop();
        ans[i] = v;

        for (int u : adj[v])
            if (--in[u] == 0)
                q.push(u);
    }

    for (i = 0; i < n; i++)
        printf("%d\n", ans[i]);

    return 0;
}

https://www.acmicpc.net/problem/2623 - 음악프로그램

정리

• 위상 정렬이 존재하기 위해서 그래프는 DAG(Directed Acyclic Graph) 여야 한다. (= 유향 그래프이며 사이클이 없어야 한다.)
• 요점 : 진입 차수를 0인 것을 제거해나가면 된다.
• 빠르게 하기 위해서 다음과 같이 할 수 있다
  • 진입 차수가 0인 목록을 큐에 넣는다.
  • 큐의 원소를 빼서 제거하면서, 진입 차수가 0이 되는 정점을 큐에 넣는다
  • 큐에서 빼는 순서가 위상 정렬의 결과다

관련 문제

• 2623 : 음악프로그램
• 2252 : 줄세우기
• 1766 : 문제집
• 1516 : 게임개발
• 1005 : ACM Craft
• 9470 : Strahler 순서
• 2637 : 장난감 조립 ★
• 3665 : 최종 순위 ★
• 2529 : 부등호 ★
• 2848 : 알고스팟어 ★
• 1948 : 임계경로 ★

참고 자료

• http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220800013823