ABC126-D : Even Relation

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

  • 평범한 Graph 탐색 문제. adj List를 구현하는게 포인트
  • 예전에 vector없이 adj 리스트 쉽게 만드는법을 배운것 같은데, 그냥 속편히 vector 쓰자.
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
#include <cstdio>
#include <vector>
using namespace std;
 
typedef struct edge {
  int dest;
  int len;
} edge;
vector<edge> adj[100001];
vector<int> ans(100001);
 
void dfs(int cur, int color) {
  ans[cur] = color;
  for(auto& e : adj[cur]) {
    if(ans[e.dest]) continue;
    if(e.len % 2) dfs(e.dest, 3-color);
    else dfs(e.dest, color);
  }
}
 
int main() {
  int N;
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    adj[a].push_back({b,w});
    adj[b].push_back({a,w});
  }
  dfs(1, 1);
  for(int i = 1; i <= N; i++)
    printf("%d\n", ans[i]-1);
}