[백준 C++] 2623 음악프로그램 - 위상정렬

2623번: 음악프로그램

#include <iostream>
#include <list>
#include <queue>
using namespace std;

list<int> Neighbors[1001];
int Entries[1001];
bool Visited[1001];
queue<int> SQ;
int Solution[1000];

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

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int Size;
		cin >> Size;
		
		int Previous;
		cin >> Previous;
		for (int j = 1; j < Size; ++j)
		{
			int Current;
			cin >> Current;
			Neighbors[Previous].emplace_back(Current);
			++Entries[Current];
			Previous = Current;
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		if (Entries[i] == 0)
		{
			SQ.emplace(i);
		}
	}

	int Cnt = 0;
	while (!SQ.empty())
	{
		int Current = SQ.front();
		SQ.pop();

		if (Visited[Current])
		{
			continue;
		}

		Visited[Current] = true;
		Solution[Cnt] = Current;
		++Cnt;

		for (const int& Neighbor : Neighbors[Current])
		{
			--Entries[Neighbor];
			if (Entries[Neighbor] == 0
				&& !Visited[Neighbor])
			{
				SQ.emplace(Neighbor);
			}
		}
	}

	if (Cnt != N)
	{
		cout << 0;
		return 0;
	}

	for (int i = 0; i < N; ++i)
	{
		cout << Solution[i] << '\n';
	}
}

---

 

위상정렬 알고리즘을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 진입 차수 배열 초기화 - 인접 리스트를 통해서 진입차수 계산 (진입차수: 자기 자신을 가리키는 에지의 개수)
2. 진입 차수가 0인 미방문 노드 선택 -> 위상 정렬 배열에 추가, 인접 노드의 진입 차수 업데이트(-1)