백준 2252 줄세우기

M번 들어오는 학생의 쌍이 다음과 같이 들어온다고 가정하자.

(3, 2)

(4, 1)

그렇다면, 3은 2보다 앞에 , 4는 1보다 앞에 있어야 한다는 뜻이다.

이를 다음과 같은 그래프로 모델링 하자

3->2

4->1

그 후 이 그래프에 대해 위상정렬을 수행하면 적절한 정답이 도출된다.

한편, 정답이 여러개인 경우 하나만 출력하라고 하였다.

이것은 edge가 없는 vertex에 대해 고려를 하지 않아도 되는 장점을 부여한다.

이를테면, 위와 같은 예가 있는데, 사실 학생의 수가 4명이 아니고 10명쯤 된다고 하자.

그렇다면 5번부터 10번까지의 학생은 indegree를 0으로 두고,

indegree순으로 위상정렬을 수행할때 5번부터 10번까지의 학생의 indegree는 0이기 때문에 먼저 출력된다.

edge가 없는 vertex에 대해 고려를 하지 않아도 되기 때문에 이것 또한 정답이 된다.

또한 아무렇게나 알고리즘을 짜면 

edge의 수가 35000, vertex의 수가 10만이기 때문에 메모리 초과나 시간 초과가 나기 쉽다.

따라서 인접행렬은 가변배열로 잡고, 

위상정렬을 수행할 때는 indegree가 0인 노드를 매번 새로 찾지 않고 위상정렬을 할 수 있게 다음과 같이 한다.

#

처음엔 indegree가 0인 노드를 indegree[N]을 순회하면서 찾는다.

그 후 위상정렬 큐(topoloQ)가 빌때까지 무한루프를 수행하는데, 

일단 위상정렬 큐의 size를 미리 저장해두고, 이 size만큼 다음의 루프를 수행한다.

##

위상정렬 큐의 머리에 있는 노드를 뽑고, 그 노드와 연결된 노드들의 indegree를 1씩 줄인다.

중요한 것은, 이때 indegree가 0이 되는 노드가 있다면 바로 위상정렬 큐에 넣는 것이다.

이렇게 함으로써 indegree가 0인 노드를 찾기 위해 N번의 루프를 수행하는것을 막는다.

##

#

이러한 알고리즘으로 비록 시간복잡도는 O(NM)이지만, 충분히 시간 안에 끝낼 수 있게 만들었다.

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>

using namespace std;

int N, M;
int indegree[35002];
vector<int> adj[35002];

int main() {
	int from, to;
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		indegree[to]++;
	}

	queue<int> topoloQ;
	queue<int> result;

	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			topoloQ.push(i);
		}
	}

	while (!topoloQ.empty()) {
		int loopcount = topoloQ.size();
		for (int loop = 0; loop < loopcount; loop++) {
			int now = topoloQ.front();
			result.push(now);
			topoloQ.pop();
			indegree[now]--;
			for (int next : adj[now]) {
				indegree[next]--;
				if (indegree[next] == 0) {
					topoloQ.push(next);
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		cout << result.front() << " ";
		result.pop();
	}

	return 0;
}