[BOJ 2623] 음악프로그램

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

---

위 문제도 위상 정렬을 해서 차례대로 출력을 하면 되는 문제이지만, 순서를 모를 경우를 예외처리해주어야 한다.

 

배열에 순서대로 위상정렬의 결과를 저장할 때 배열의 길이와 전체 가수의 개수가 맞지 않는다면 제대로 된 순서를 모르는 것이기 때문에 이를 예외처리해주면 된다.

---

#include <stdio.h>
#include <vector>
#include <queue>

#define max(a, b) ((a) > (b) ? (a) :(b))

using namespace std;

int n, m;
int indgree[1001];
int ans[1001];

int main()
{
	int ansCnt = 0;
	vector<vector<int>> g;
	scanf("%d%d", &n, &m);
	g.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int k, pre = -1;
		scanf("%d",&k);
		for (int j = 0; j < k; j++)
		{
			int a;
			scanf("%d", &a);
			if (pre != -1)
			{
				g[pre].push_back(a);
				indgree[a]++;
			}
			pre = a;
		}
	}

	queue<int> q;

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

	while (!q.empty())
	{
		int p = q.front(); q.pop();
		ans[ansCnt++] = p;

		for (auto s = g[p].begin(); s != g[p].end(); s++)
		{
			if (--indgree[*s] == 0)
				q.push(*s);
		}
	}

	if (ansCnt == n)
	{
		for (int i = 0; i < ansCnt; i++)
		{
			printf("%d\n", ans[i]);
		}
	}
	else
		printf("0");
}