[기본문제풀이] topology_sort

풀이 일시 : 2020-08-16

​

위상정렬 :

순서가 정해져 있는 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 큐 사용

​

문제 :

topology sort 수행

​

시간복잡도 :

O(V+E)

​

풀이 : 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10

using namespace std;

int n, inDegree[MAX];
vector<int> a[MAX];

void topologySort() {
	int result[MAX];
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) q.push(i); //처음에 큐에 넣을것. 진입차수0
	}
	for (int i = 1; i <= n; i++) {
		if (q.empty()) { //다 돌기전에 큐가 빈것.
			printf("사이클이 발생했습니다");
			return;
		}
		int x = q.front(); //현재 진입차수 0인거 큐에서 뺀다
		q.pop();
		result[i] = x;

		for (int i = 0; i < a[x].size(); i++) { //연결된걸 둘러보며
			int y = a[x][i]; 
			if (--inDegree[y] == 0) //진입차수 빼준게 0이면 큐에들어간다
				q.push(y);
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d", result[i]);
	}
}

int main(void) {
	n = 7;
	a[1].push_back(2);
	inDegree[2]++;
	a[1].push_back(5);
	inDegree[5]++;
	a[2].push_back(3);
	inDegree[3]++;
	a[3].push_back(4);
	inDegree[4]++;
	a[4].push_back(6);
	inDegree[6]++;
	a[5].push_back(6);
	inDegree[6]++;
	a[6].push_back(7);
	inDegree[7]++;
	topologySort();
}