[C++] 위상 정렬(Topological Sort)

위상 정렬(Topological Sort)

위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다.

• 여러 개의 답이 존재할 수 있다.
• DAG(Directed Acyclic Graph)에만 적용이 가능하다.
• 스택과 큐로 구현된다.

 

기본 원리

1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7

• 진입 차수가 0인 정점을 큐에 삽입한다.
• 큐에서 원소를 꺼내 연결된 모든 간선을 제거 후 진입 차수가 0이 된 정점을 큐에 삽입한다.
• 큐가 빌 때까지 2번 과정을 반복한다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

 

문제

 

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

1766번: 문제집

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

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

	int n, m;
	cin >> n >> m;

	vector<int> graph[32001];
	vector<int> degree(n + 1, 0);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		degree[b]++;
	}

	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 1; i <= n; i++)
		if (degree[i] == 0)
			pq.push(i);

	while (!pq.empty()) {
		int top = pq.top();
		cout << top << ' ';
		pq.pop();

		for (int i : graph[top]) {
			degree[i]--;
			if (degree[i] == 0)
				pq.push(i);
		}
	}
}

 

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

3665번: 최종 순위

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

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

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n;

		int lastYearScore[501]{};
		for (int i = 0; i < n; i++)
			cin >> lastYearScore[i];

		bool graph[501][501]{};
		int degree[501]{};
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++) {
				graph[lastYearScore[i]][lastYearScore[j]] = true;
				degree[lastYearScore[j]]++;
			}

		cin >> m;
		while (m--) {
			int a, b;
			cin >> a >> b;

			if (graph[a][b]) {
				graph[b][a] = true;
				graph[a][b] = false;
				degree[a]++;
				degree[b]--;
			}
			else {
				graph[a][b] = true;
				graph[b][a] = false;
				degree[a]--;
				degree[b]++;
			}
		}

		queue<int> q;
		for (int i = 1; i <= n; i++)
			if (degree[i] == 0)
				q.push(i);

		vector<int> answer;
		while (!q.empty()) {
			int f = q.front();
			q.pop();
			answer.push_back(f);

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

		if (answer.size() == n) {
			for (int j = 0; j < n; j++)
				cout << answer[j] << ' ';
			cout << endl;
		}
		else
			cout << "IMPOSSIBLE" << endl;
	}
}