[백준 BOJ] 2623번 - 음악프로그램 (C++)

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

줄세우기와 마찬가지로 위상정렬을 사용하면 쉽게 풀 수 있는 문제이다. 주의할 사항으로는 모든 가수가 pd들이 적어 놓은 숫자에 나타나지 않을 수 있다는 점과, 싸이클이 존재해 위상정렬이 안 될 수도 있다는 점, 마지막으로 중복된 간선이 존재할 수 있다는 점이다. 이에 유의하여 입력을 받고 위상정렬을 사용하면 된다. 

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <set>
#include <queue>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int N, M;
vector<int> pd[100];
set<int> edge[1001];
int totalEdge[1001];
vector<int> ans;
void topoloySort(int i)
{
    queue<int> q;
    q.push(i);
    while (!q.empty())
    {
        int num = q.front();
        totalEdge[num]=-1;
        ans.push_back(num);
        q.pop();
        for (auto j : edge[num])
        {
            if(totalEdge[j]<0)
                continue;
            if (--totalEdge[j] == 0)
            {   
                q.push(j);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    int n;
    for (int i = 0; i < M; i++)
    {
        cin >> n;
        int c;
        for (int j = 0; j < n; j++)
        {
            cin >> c;
            pd[i].push_back(c);
        }
    }
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < pd[i].size() - 1; j++)
        {
            edge[pd[i][j]].insert(pd[i][j + 1]);
        }
    }
    for(int i = 1; i<=N; i++){
        if(!edge[i].empty()){
            for(auto i : edge[i]){
                totalEdge[i]++;
            }
        }
    }
    for (int i = 1; i <= N; i++)
    {
        if (totalEdge[i] == 0)
        {
            topoloySort(i);
        }
    }
    for(int i = 1; i<=N; i++){
        if(totalEdge[i]>=0)
        {
            cout<<0<<endl;
            return 0;
        }
    }
    for(auto i : ans)
        cout<<i<<endl;
    return 0;
}