BOJ 9466: 텀 프로젝트

작성일

https://www.acmicpc.net/problem/9466

  • 3월동안 210문제 풀기 (10/210)
  • 위상정렬로 사이클 찾기, DFS로도 당연히 가능 (BackEdge 찾으면 됨)
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
#include <bits/stdc++.h>
using namespace std;

struct Graph {
  int N;
  vector<vector<int>> adj;
  vector<int> indegree;

  Graph(int n): N(n), adj(n+1), indegree(n+1) {}
  void addEdge(int u, int v) {
    adj[u].push_back(v);
    indegree[v]++;
  }

  int topologicalSort() {
    queue<int> q;
    for(int i = 1; i <= N; i++)
      if(indegree[i] == 0)
        q.push(i);

    int cnt = 0;
    while(q.size()) {
      int u = q.front();
      q.pop();
      cnt++;

      for(int v: adj[u]) {
        if(--indegree[v] == 0)
          q.push(v);
      }
    }
    return cnt;
  }
};


int main() {
  int TC, N, v;
  scanf("%d", &TC);
  while(TC--) {
    scanf("%d", &N);
    Graph graph(N);
    for(int u = 1; u <= N; u++) {
      scanf("%d", &v);
      graph.addEdge(u, v);
    }

    int cnt = graph.topologicalSort();
    printf("%d\n", cnt);
  }
}