반응형

문제 출처 :


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;
}
cs


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[SwExpertAcademy] Inversion Counting  (0) 2019.08.18
[17254번] 키보드 이벤트  (0) 2019.08.10
[1251번] 하나로  (0) 2019.08.05
[4803번] 트리  (4) 2019.08.03
[1245번] 균형점  (0) 2019.07.31