[백준/BOJ] 백준 2623번 : 음악프로그램

www.acmicpc.net/problem/2623

2623번: 음악프로그램

위상정렬을 이용해 문제를 해결한다 결과로 나온 순서의 길이가 n이 맞는지를 확인하여 순서를 정하는것이 가능한지 확인한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int> indegree(1001, 0);
vector<int> adj[1001];

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int num;
		vector<int> singer_list;

		cin >> num;

		for (int j = 0; j < num; j++)
		{
			int singer;

			cin >> singer;
			singer_list.push_back(singer);
		}

		for (int j = 0; j < singer_list.size(); j++)
		{
			if (j != 0) //해당 보조PD의 첫번째 가수가 아닐때
			{
				indegree[singer_list[j]]++;
			}

			if (j != singer_list.size() - 1) //해당 보조PD의 마지막 가수가 아닐때
			{
				adj[singer_list[j]].push_back(singer_list[j + 1]);
			}
		}
	}

	//위상정렬을 이용해 문제를 해결한다
	queue<int> q;
	vector<int> result;

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

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

		result.push_back(here);

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0)
				q.push(there);
		}
	}

	if (result.size() != n) //순서를 정하는것이 불가능 할때
		cout << 0;
	
	else
	{
		for (int i = 0; i < result.size(); i++)
			cout << result[i] << "\n";
	}

	return 0;
}