위상정렬 알고리즘

#

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

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

##

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

한편, 방금 뽑은 노드의 indegree도 1을 줄인다.

이때 indegree가 0이 되는 노드가 있다면 바로 위상정렬 큐에 넣는다.

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

##

#

추가로, 방향그래프에서 모든 노드를 탐색하지 않았는데 큐가 비어있다면

그 그래프는 사이클이 있는 것이다. 

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

int main() {
	queue<int> topoloQ;
	queue<int> result;

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

	while (!topoloQ.empty()) {
		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;
}