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

이 문제는 가수들 간의 관계가 출연 순서로 나타내어지고 있다. 따라서, 방향 그래프로 표현이 가능하다.
이때, 보조 PD가 가수들의 순서를 정해두면, 이 순서를 지키면서 전체 순서를 정하는 것이다.

이는 그래프 정점들의 순서를 결정하는 것과 동일한 상황이므로 위상 정렬으로 문제를 해결할 수 있음을 의미한다.

따라서, 위상 정렬로 문제를 접근해보자. 이 때, 사이클이 없는 방향 그래프여야 위상 정렬이 가능하므로 위상 정렬이 불가능하다면 $0$을 출력하도록 문제에서 요구하고 있다.

이를 바탕으로 코드를 작성해보자.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int deg[1001];
vector<int> adj[1001], res;
queue<int> q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		int sz, u, v;
		cin >> sz >> u;
		while (--sz) {
			cin >> v;
			adj[u].push_back(v);
			deg[v]++;
			u = v;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (!deg[i]) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		res.push_back(cur);
		for (int nxt : adj[cur]) {
			deg[nxt]--;
			if (!deg[nxt]) q.push(nxt);
		}
	}

	if (res.size() != n) cout << 0;
	else {
		for (int e : res) cout << e << "\n";
	}
}