백준(BOJ) 2623 음악프로그램 ***

# 위상정렬

Indegree를 이용한 위상정렬을 이용하여 구현하였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <utility>
#include <functional>
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int n, m,a,b,c,node[32005];
vector<int> vert[32005],ans;
priority_queue<int,vector<int>,greater<int>> pq;
// 우선순위 큐를 사용하는 대신 그냥 큐를 사용해도된다.
// 우선순위 큐를 사용하면 향하는 간선이 없는 노드들 중에 가장 작은 노드를 먼저 출력.

int main()
{
	fill_n(&node[0], 32005, 0);
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &a,&b);
		for (int k = 0; k < a-1; k++)
		{
			scanf("%d", &c);
			vert[b].push_back(c);
			// b->c를 향하는 간선을 저장한다.
			node[c]++;
			// c 노드에 향하는 간선의 개수를 저장한다.
			b = c;
		}
	}
	// 입력을 받아 온다.

	for (int i = 1; i <= n; i++)
		if (node[i] == 0)
			pq.push(i);
	// 해당 노드에 향하는 간선이 0인경우 시작지점 으로 간주하고 pq에 추가한다.
	
	while (!pq.empty())
	{
		int cur = pq.top();
		pq.pop();
		// 시작지점중 가장 작은 값을 가져온다.

		while (!vert[cur].empty())
		{
			int tmp = vert[cur].back();
			vert[cur].pop_back();
			node[tmp]--;
			if (node[tmp] == 0)
				pq.push(tmp);
		}
		// 시작지점 다음 노드 중에 해당 노드를 향하는 간선이 없으면 pq에 추가해준다.

		ans.push_back(cur);
	}
	for(int i=1;i<=n;i++)
		if (node[i] != 0)
		{
			printf("0");
			return 0;
		}
	// 노드끼리 순환을하여 위상졍렬의 조건을 위반하면 0을 출력해주고 끝낸다.

	for (int i = 0; i < ans.size(); i++)
		printf("%d\n", ans[i]);
	return 0;
}