[코드업] 3212 : 위상 정렬(topological sort) (C)

알고리즘

위상정렬

풀이

위상정렬을 하 되, 우선순위가 같은 경우 작은 숫자부터 출력해야 하기 때문에 한번의 시행이 끝날 때 마다 다음 시행할 '한 개'의 숫자를 Queue에 넣어준다.

( 이런 우선순위 조건이 없을 경우엔 간선이 지워지는 노드들만 확인 하면 된다. )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<iostream> #include<queue> #include<algorithm> #include<vector> using namespace std;   queue<int> q; queue<int> ans; vector<int> vec[201];   int ind[201];     int main(){       int v,n;     cin>>v>>n;     for(int i=0;i<n;i++){         int a,b;         cin>>a>>b;         vec[a].push_back(b);         ind[b]++;             }          for(int i=1;i<=v;i++){         if(ind[i]==0)             q.push(i);     }       while(!q.empty()){         int size=q.size();           for(int i=0;i<size;i++){             int tmp=q.front();             ind[tmp]--;             ans.push(tmp);             q.pop();                          for(int i=0;i<vec[tmp].size();i++){                 ind[vec[tmp][i]]--;             }                      }                  for(int i=1;i<=v;i++)             if(ind[i]==0){                 q.push(i);                 break;             }                      }     if(ans.size()!=v)         cout<<"-1";     else{         while(!ans.empty()){             cout<<ans.front()<<"\n";             ans.pop();         }     }      }