ABC126-E : 1 or 2

작성일

https://atcoder.jp/contests/abc126/tasks/abc126_e

  • 뭔가 복잡하게 써놓았지만 결국은 연결성 판단 문제이다. union-find나 dfs로 풀 수 있다.
  • dfs는 종료조건을 먼저 체크해야 짧아진다.
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
#include <cstdio>
#include <vector>
using namespace std;

class Problem {
 public:
  int N, M, x, y, z;
  vector<int> adj[100002];
  vector<int> visit;
  
  Problem() {
    scanf("%d%d", &N, &M);
    visit = vector<int>(N+10);
    for(int i = 0; i < M; i++) {
      scanf("%d%d%d", &x, &y, &z);
      adj[x].push_back(y);
    }
  }

  int dfs(int n) {
    if (visit[n]++) return 0;
    for(int d: adj[n]) dfs(d);
    return 1;
  }
  
  void solve() {
    int ans = 0;
    for(int i = 1; i <= N; i++)
      ans += dfs(i);
    printf("%d", ans);
  }
};

int main() {
  Problem().solve();
}