BOJ #2623: 음악 프로그램

쉬운 목차

문제

제2623호: 음악 프로그램

가수 N의 수와 보조 PD의 수 M은 첫 줄에 주어진다. 가수는 숫자 1, 2, … 이며 N으로 표시됩니다. 두 번째 줄부터 각 보조 PD가 지정한 순서가 한 줄에 하나씩 나타납니다. 각 줄의 시작 부분에는 보조 PD의 직함이 있습니다.

www.acmicpc.net

설명

어시스트 PD가 설정한 차수를 모두 만족하는 최종 차수를 찾아야 하므로 위상 정렬 문제를 해결했습니다!

이미 입력된 주문쌍은 다시 입력할 수 있습니다. 이를 중복 처리하지 않기 위해 설정했습니다!

#include <iostream>
#include <queue>
#include <set>
#define MAX_M 101
#define MAX_N 1001
using namespace std;

int N, M;
int inDegree(MAX_N);
set<int> list(MAX_N);

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();
}