[c++] 위상정렬(그래프정렬)

위상정렬(그래프정렬)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
	freopen("input.txt", "rt", stdin);
    int n, m, a, b;
    cin>>n>>m;
    vector<vector <int> > graph(n+1, vector<int>(n+1, 0));
    vector<int> degree(n+1);
    queue<int> Q;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        graph[a][b]=1;
        degree[b]++;
    }
    for(int i=1; i<=n; i++){
        if(degree[i]==0) Q.push(i);
    }
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        cout<<now<<" ";
        for(int i=1; i<=n; i++){
            if(graph[now][i]==1){
                degree[i]--;
                if(degree[i]==0) Q.push(i);
            }
        }
    }
    return 0;
}

graph배열에 선후관계에 있는 것들을 1로 표시해준다.

그러면서 후순위에 있는 b를 인덱스로해서 degree함수에 1씩 더해준다. 

후순위에 있어서 degree배열에서 숫자가 높으면 높을수록 가장 나중에 처리해야 하는 일이 된다.

 

이렇게 가장 나중에 처리해야할 일들을 표시하는데 만약 값이 0이라면 이것보다 앞에 처리해야할 일은 없으므로

Q에 넣어준다.

Q에 넣은 값들이 없을때까지 while문을 돌면서 pop된 값을 출력하고

해당 값을 now에 할당해서 그 값의 화살표를 받는 값이 있다면 degree에서 그 값을 인덱스로하는 곳을 1씩 빼준다.

1을 빼주었을 때 0이 된다면 그 값을 Q에 push한다. 

이렇게 반복해서 출력하면 전체 일의 순서를 출력할 수 있다.