BOJ 2623번: 음악프로그램

문제

문제 바로가기> BOJ 2623번: 음악프로그램

2623번: 음악프로그램

 

풀이

보조 PD들이 정해 놓은 순서를 모두 만족 시키는 최종 순서를 찾아야 하기 때문에 위상정렬을 이용해서 문제를 풀었다!
주의 할 점은 이미 들어온 순서 쌍이 또 들어올 수 있다는 점이다. 이를 중복 처리 해주지 않기 위해 set을 이용했다!
 

#include <iostream>
#include <queue>
#include <set>
#define MAX 1001
using namespace std;

int N, M;
int inDegree[MAX];
set<int> list[MAX];

void input()
{
    cin >> N >> M;

    int singerNum, num;
    for (int i = 0; i < M; i++)
    {
        cin >> singerNum;
        int a, b;
        cin >> a;
        while (--singerNum)
        {
            cin >> b;
            if (list[a].find(b) == list[a].end())
                inDegree[b]++;
            list[a].insert(b);
            a = b;
        }
    }
}

void solution()
{
    queue<int> q, ans;
    for (int i = 1; i <= N; i++)
    {
        if (inDegree[i] == 0)
        {
            q.push(i);
            ans.push(i);
        }
    }

    while (!q.empty())
    {
        int n = q.front();
        q.pop();
        for (auto next : list[n])
        {
            if (--inDegree[next] == 0)
            {
                q.push(next);
                ans.push(next);
            }
        }
    }

    if (ans.size() != N)
        cout << 0;
    else
    {
        while (!ans.empty())
        {
            cout << ans.front() << "\n";
            ans.pop();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    input();
    solution();
}