[백준 C++]2252번: 줄세우기(위상정렬)

1.문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

2. Solved.ac 난이도

3. 활용 알고리즘:  DAG+ 위상정렬

4. 틀린 이유: TLE 

큐에 넣지 않고 그때그때 가장 작은 depth를 가지는 노드를 찾으려는 몽총한 생각을 했음

---

최종 정답 코드

위상정렬을 위해서, 앞에 서야하는 a가 b를 가리키는 형태로 그래프를 만들어 비순환 방향그래프를 만들었다.

depth가 0인것( 노드로 들어오는 간선이 하나도 없는 것) 부터 차례로 큐에 담아 출력해주었고, 출력해준 노드가 가리키는 노드들의 depth를 1씩 줄여주는 것을 반복하며 모든 노드 n개를 출력해 주었다.

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

vector<int>sucnode[32001];
int edge[32001];
queue<int> q;
//priority_queue <vector<pair<int,int>>, pair<int, int>,greater> pq;

void topologySort() {
	while (!q.empty()) {
		int point = q.front();
		q.pop();
		for (int i = 0; i < sucnode[point].size(); i++) {
			edge[sucnode[point][i]]--;
			if (edge[sucnode[point][i]] == 0) {
				q.push(sucnode[point][i]);
			}
		}
		edge[point]--;
		cout << point<<" ";
	}
	return;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m,a,b;
	cin >> n >>  m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		sucnode[a].push_back(b);
		edge[b]++;
	}
	for (int i = 1; i <= n; i++){
		if (edge[i] == 0) {
			q.push(i);
		}
	}
	topologySort();
	return 0;
}