위상 정렬(Topological Sort)

// 위상정렬
// 순서가 정해져있는 작업을 차례대로 수행해야 할 때 사용
// non cycle & direct graph

// 알고리즘 순서
// 진입차수 : 한 정점으로 들어오는 다른 정점의 갯수
// 1. 진입차수가 0인 정점을 queue에 삽입
// 2. queue에서 정점을 꺼내 연결된 모든 간선을 제거
// 3. 간선 제거 이후에 진입차수가 0이 된 정점을 다시 queue에 넣어준다 ==> 항상 진입차수가 0인 정점만 큐에 삽입한다
// 4. 2,3번을 반복, 모든 정점을 방문하기 전에 queue가 빈다면 사이클이 존재하는 것이고, 모든 정점을 방문했다면 queue에서 꺼낸 순서가 위상정렬의 순서

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

#define MAX 10

int n, inDegree[MAX]; // inDegree : 진입차수를 의미
vector<int> a[MAX];

void wsort() {
	int result[MAX];
	queue<int> q;

	//진입 차수가 0인 노드를 queue에 삽입
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	//위상 정렬이 완전히 수행하려면 정확히 N개의 노드를 방문
	for (int i = 1; i <= n; i++) {
		// N개를 방문하기 전에 queue가 빈다면 사이클이 발생 -> 위상정렬 불가능
		if (q.empty()) return;

		int x = q.front();
		q.pop();
		result[i] = x; // queue에서 꺼낸 x는 위상정렬의 순서를 지키고 있는 노드
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (--inDegree[y] == 0) q.push(y); // 진입을 제거해주고 차수가 0이면 queue에 삽입
		}
	}

	// 순서 출력
	for (int i = 1; i <= n; i++) {
		printf("%d ", result[i]);
	}
}