[ORDERING] 할 일 순서 정하기

• 분류: 구현, 그래프
• 입력: 테스트 케이스 C(<=50), 작업의 개수 N(1<=N<=26), 의존 관계의 수 M(1<=M<=100), 각 작업은 알파벳 대문자 A 이후 글자 표현 (예를 들어 AB형태로 주어지면 A->B 작업이 이루어줘야한다.)
• 출력: 작업을 수행할 수 있는 순서를 출력. 여러가지가 있다면, 이중 사전 순으로 가장 앞에 있는 것을 출력
• 소스코드

?

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 62 63 64 65

#include <iostream> #include <fstream> #include <queue> #include <vector> #include <string> #include <functional> using namespace std;   vector<vector<bool> > adj; vector<int> indegree; vector<char> topological(int);   int main(){     ios::sync_with_stdio(false);       ifstream in("in.txt");     int C;     in >> C;     while (C--){         int N, M;         in >> N >> M;           adj = vector<vector<bool> >(N, vector<bool>(N, false));         indegree = vector<int>(N, 0);           string str;         for (int i = 0; i < M; i++){             in >> str;             adj[str[0] - 'A'][str[1] - 'A'] = true;             indegree[str[1] - 'A']++;         }           vector<char> ret = topological(N);           for (int i = 0; i < N; i++)             cout << ret[i];           cout << endl;     }     system("pause");     return 0; }   vector<char> topological(int n){     priority_queue<char, vector<char>, greater<char> > pq;     vector<char> ordering;       for (int i = 0; i < n; i++)         if (indegree[i] == 0) pq.push(i + 'A');       while (!pq.empty()){         int here = pq.top() - 'A';         pq.pop();           ordering.push_back(here + 'A');         for (int i = 0; i < n; i++){             if (adj[here][i]){                 if(--indegree[i] == 0)                     pq.push(i + 'A');             }         }     }       return ordering; }

• 소스설명: 
topological(int n): 위상정렬을 이용한 구현이다. 사전 순으로 나와야 하므로 priority queue를 사용하며, greater로 오름차순으로 출력이 된다. 모든 상황은 성립이 되므로 종료조건은 priority queue가 비어 있으면 종료된다.


• 참고문제: https://algospot.com/judge/problem/read/ORDERING#