문제
문제로 이동> BOJ #2623: 음악 프로그램
설명
어시스트 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();
}