[백준] 2252번 줄 세우기 (C++)

문제

 

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

풀이

이 문제는 위상 정렬을 사용하여 풀이했다.

 

위상 정렬이란 ?

• 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다.

위상 정렬을 사용하기 위해서는 조건이 필요하다.

1. 방향 그래프(Directed Graph)여야 한다.
2. 비순환 그래프(Acyclic Graph)여야 한다. 즉, 사이클이 없어야 한다.
3. 최소한 하나의 위상 정렬 결과가 존재해야 한다.

이 문제는 위 조건에 만족하기 때문에 위상 정렬을 사용하여 풀이했다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int degree[32001];
vector <int> vec[32001];

void Topological_Sort() {
	queue<int> q;

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

	while (!q.empty()) {
		int front = q.front();
		cout << front << " ";
		q.pop();

		for (int i = 0; i < vec[front].size(); i++) {
			degree[vec[front][i]]--;

			if (degree[vec[front][i]] == 0) {
				q.push(vec[front][i]);
			}
		}
	}
}
int main() {
	cin >> n >> m;


	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		degree[y]++;

		vec[x].push_back(y);
	}

	Topological_Sort();

	return 0;
}