BOJ4803: 트리

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

  • Simple tree travel problem.
  • Need to check DFS’s edge classification condition.
  • How to solve with Disjoint-set?
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
#include <bits/stdc++.h>
using namespace std;

class Graph {
  vector<vector<int>> adj;
  vector<int> pre, post;
public:
  Graph(int N): adj(N+1), pre(N+1), post(N+1) {}
  void addEdge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  bool dfs(int x, int p = -1) {
    if(post[x]) return false;
    pre[x] = true;
    for(int near: adj[x]) {
      if(!post[near] && pre[near] && near != p)
        return false;
      if(!pre[near])
        if (!dfs(near, x))
          return false;
    }
    post[x] = true;
    return true;
  }
};

int main() {
  int N, M, a, b;
  for(int tc = 1; ;tc++) {
    scanf("%d%d", &N, &M);
    if(!N && !M) return 0;
    Graph g(N);
    for(int i = 0; i < M; i++) {
      scanf("%d%d", &a, &b);
      g.addEdge(a, b);
    }
    int ans = 0;
    for(int i = 1; i <= N; i++)
      ans += g.dfs(i);
    if(ans == 0)
      printf("Case %d: No trees.\n", tc);
    else if(ans == 1)
      printf("Case %d: There is one tree.\n", tc);
    else
      printf("Case %d: A forest of %d trees.\n", tc, ans);
  }
}