BOJ #2623: 음악 프로그램

쉬운 목차

문제

문제로 이동> 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(); }