[BAE/<JOON> 문제풀이] 2252. 줄세우기

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

2252번: 줄 세우기

 

핵심::
위상정렬 기본 문제

 

풀이::

학생 순서가 단편적으로 정해져있고 정해진 순섬나 해치지 않는다면 어떤 순서로 배열해도 상관없다.

 

그냥 위상 정렬하고 정해지지 않은 순서는 번호 순으로 출력한다.

 

코드::

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

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> arr(n + 1);
	vector<int> en(n + 1, 0);
	for (int i = 1; i <= m; i++) {
		int s, e;
		cin >> s >> e;
		arr[s].push_back(e);
		en[e]++;
	}

	queue<int> q;

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

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (auto nv : arr[cur]) {
			if (--en[nv] == 0) {
				q.push(nv);
				cout << nv << " ";
			}				
		}
	}

	return 0;
}