백준 #2623 음악프로그램

백준 #2623 음악 프로그램

위상 정렬을 사용한 문제.

위상 정렬에 관한 설명

인접 리스트를 사용해 그래프를 입력받고 위상 정렬을 사용해 적절한 순서로 출력한다. M명의 보조 PD가 정한 순서를 그래프로 구성하면 일반적인 위상 정렬 문제가 된다.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> graph(N + 1);
    vector<int> inDegree(N + 1, 0);
    for (int i = 0; i < M; i++) {
        int singerCount;
        cin >> singerCount;
        int from, to;
        cin >> from;
        while (singerCount-- > 1) {
            cin >> to;
            graph[from].push_back(to);
            inDegree[to]++;
            from = to;
        }
    }
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= N; i++) {
        if (!inDegree[i]) {
            q.push(i);
        }
    }
    for (int i = 1; i <= N; i++) {
        if (q.empty()) {
            ans.clear();
            ans.push_back(0);
            break;
        }
        int num = q.front();
        q.pop();
        ans.push_back(num);
        for (int j = 0; j < graph[num].size(); j++) {
            int next = graph[num][j];
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }
    for (auto &num : ans) {
        cout << num << '\n';
    }
    return 0;
}