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

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

2252번: 줄 세우기

각 쌍들 간의 관계로 키를 작은 순서대로 세운다.

>> Topological Sort를 떠올릴 수 있다.

 

[AC 코드]

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

int n, m;
int inDegree[32001];
vector<int> adj[32001];
vector<int> result;

void topologicalSort() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (inDegree[i] == 0) {
			q.push(i);
			result.push_back(i);
		}
	}

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < adj[now].size(); ++i) {
			int next = adj[now][i];
			if (--inDegree[next] == 0) {
				q.push(next);
				result.push_back(next);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		inDegree[b]++;
	}

	topologicalSort();

	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << ' ';
	}

	return 0;
}