[백준 C++] 2252 줄 세우기 - 위상정렬

2252번: 줄 세우기

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

vector<list<int>> Neighbors;
vector<int> Entries;
vector<int> Sequence;
queue<int> SearchQueue;

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

	int N, M;
	cin >> N >> M;

	Neighbors.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Neighbors.emplace_back(list<int>());
	}

	Entries.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Entries.emplace_back(0);
	}

	for (int i = 0; i < M; ++i)
	{
		int A, B;
		cin >> A >> B;

		Neighbors[A - 1].emplace_back(B - 1);
		++Entries[B - 1];
	}

	int i = 0;
	for (int& Entry : Entries)
	{
		if (Entry == 0)
		{
			SearchQueue.push(i);
		}

		++i;
	}

	Sequence.reserve(N);
	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.front();
		SearchQueue.pop();

		Sequence.emplace_back(Current);
		for (const int& Neighbor : Neighbors[Current])
		{
			--Entries[Neighbor];
			if (Entries[Neighbor] == 0)
			{
				SearchQueue.push(Neighbor);
			}
		}
	}

	for(const int& Student : Sequence)
	{
		cout << Student + 1 << ' ';
	}
}

---

해당 문제는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 문제로

위상 정렬 알고리즘을 사용해서 다음과 같은 단계로 풀었습니다.

 

1. 인접 리스트를 통해서 진입차수 계산

2. 진입 차수가 0인 미방문 노드 선택 후 위상 정렬 배열에 추가

3. 해당 노드의 인접 노드들의 진입 차수 업데이트

4. 모든 노드가 위상 정렬 배열에 추가될 때까지 2~3번 반복