[SwExpertAcademy] 줄세우기

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxxwaaAgADFAW4

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상정렬

위상 정렬을 통해 문제를 해결 할 수 있다.

자세한 내용은 아래 위상정렬 코드를 확인해보자.

https://www.crocus.co.kr/search/위상정렬

소스 코드 : 

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 66 67

#include <iostream> #include <vector> #include <queue>   using namespace std;   vector<int> vc[50002]; int indegree[50002];   void init() {   for (int i = 0; i < 50002; i++) {     vc[i].clear();     indegree[i] = 0;   }    }   int main() {   int tCase;   scanf("%d", &tCase);     for (int tc = 1; tc <= tCase; tc++) {     init();       int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < m; i++) {       int from, to;       scanf("%d %d", &from, &to);         vc[from].push_back(to);       indegree[to]++;     }       queue<int> q;     vector<int> ans;     for (int i = 1; i <= n; i++)       if (!indegree[i]) {         q.push(i);       }       while (!q.empty()) {       int here = q.front();       q.pop();         ans.push_back(here);         for (int i = 0; i < vc[here].size(); i++) {         int next = vc[here][i];           indegree[next]--;         if (!indegree[next])            q.push(next);       }     }       printf("#%d ",tc);     for (int i = 1; i <= n; i++) {       if (indegree[i])         return !printf("ERROR\n");         printf("%d ", ans[i - 1]);     }     printf("\n");   }   return 0; } Colored by Color Scripter

cs