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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
int N = 0;
int M = 0;
int arr[1001] = {};
int child[1001] = {};
std::vector<int> parent[1001] = {};
 
int main() 
{
	std::cin >> N >> M;
 
	for (int i = 0; i < M; ++i)
	{
		int num = 0;
		std::cin >> num;
 
		int prev = 0;
		int next = 0;
		for (int j = 0; j < num; ++j)
		{
			if (!prev)
			{
				std::cin >> prev;
			}
 
			else
			{
				std::cin >> next;
				++child[next];
				parent[prev].push_back(next);
				prev = next;
			}
		}
	}
 
	std::queue<int> que = {};
 
	for (int i = 1; i <= N; ++i)
	{
		if (!child[i])
		{
			que.push(i);
		}
	}
 
	std::vector<int> ans = {};
 
	while (!que.empty())
	{
		int now = que.front();
		que.pop();
 
		ans.push_back(now);
 
		for (int i = 0; i < parent[now].size(); ++i)
		{
			int next = parent[now][i];
			if (child[next])
			{
				--child[next];
 
				if (!child[next])
				{
					que.push(next);
				}
			}
		}
	}
 
	if (ans.size() == N)
	{
		for (int i = 0; i < ans.size(); ++i)
		{
			std::cout << ans[i] << "\n";
		}
	}
 
	else
		std::cout << 0;
 
	return 0;
}

 

위상알고리즘 입니다.

부모를 하나 추가해주고, 본인의 부모를 알 수 있도록 넣어줍니다.

연결이 하나도 되지 않은 것들은 바로 큐에 넣어서 빠질 수 있도록 하고 순서대로 돌아가면서 계산합니다.

이전 것과 비교해서 안될 가능성이 있다는 것이 중요합니다.

전부 끝났을 때 모두 다 설정이 되었다면 출력, 없다면 0을 출력합니다.