문제 간략 설명

N명의 가수가 있고, M명의 보조 PD가 각각 자신이 담당한 가수들의 출연 순서를 정해온다. 이 모든 조건을 만족하는 전체 가수의 출연 순서를 정해야 한다. 불가능한 경우 0을 출력한다.

풀이 방법

  1. 입력에 대해서 단방향 그래프로 vector<vector<int>> graph에 저장
  2. 진입 차수에 대해서 vector<int> counts에 저장
  3. queue에 counts가 0인 노드들을 push하고, queue에서 하나씩 빼면서 처리한다.
  4. 빼낸 노드에 대해 graph를 돌면서 진입차수(counts)를 하나씩 빼주고, 0이 되면 queue에 push한다.
  5. queue가 empty일 때까지 돌고 결과가 N개가 되면 순서대로 출력. N개 안 되면 불가능으로 0 출력한다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
int cnt = 0;

vector<vector<int>> input;
vector<vector<int>> graph;
vector<int> res;
vector<int> counts;
queue<int> q;

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

	cin >> N >> M;

	input.resize(M);

	for (int i = 0; i < M; i++) {
		int temp;

		cin >> temp;

		input[i].resize(temp);

		for (int j = 0; j < temp; j++)
			cin >> input[i][j];
	}

	graph.resize(N);
	counts.resize(N, 0);

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < input[i].size() - 1; j++) {
			int cur = input[i][j] - 1, next = input[i][j + 1] - 1;
			graph[cur].push_back(next);
			counts[next]++;
		}
	}

	for (int i = 0; i < N; i++)
		if (counts[i] == 0)
			q.push(i);

	while (!q.empty()) {
		int n = q.front();

		for (int i = 0; i < graph[n].size(); i++) {
			int next = graph[n][i];
			counts[next]--;
			if (counts[next] == 0)
				q.push(next);
		}

		res.push_back(n + 1);
	
		q.pop();
	}

	if (res.size() != N) {
		cout << "0\\n";
		return 0;
	}

	for (auto n: res)
		cout << n << endl;
	
	return 0;
}

Key Points