[백준] 2623번 Gold 3 음악프로그램, C++

 

위상정렬 문제이다.

방향 그래프여야 하고, 사이클이 없어야 한다.

그래프 문제와 다른 점은, 문제에 조건에 맞는 순서를 출력하는 점이라고 생각하면 된다.

 

본인은 BFS 방식으로 풀었다.

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

#define endl "\n"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(1001);
    vector<int> indegree(1001, 0);

    queue<int> q;
    vector<int> result;

    for (int i = 0; i < m; i++) {
        int seq;
        cin >> seq;

        int prev = 0;
        for (int j = 0; j < seq; j++) {
            int num;
            cin >> num;

            if (prev == 0) {
                prev = num;
                continue;
            }

            adj[prev].push_back(num);
            indegree[num]++;
            prev = num;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int prev = q.front();
        q.pop();

        for (int next : adj[prev]) {
            indegree[next]--;

            if (indegree[next] == 0) {
                q.push(next);
            }
        }

        result.push_back(prev);
    }

    if (result.size() == n) {
        for (int r : result) {
            cout << r << endl;
        }
    } else {
        cout << 0 << endl;
    }
}