[ORDERING] 할 일 순서 정하기

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

#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#