AtCoder ABC 126 D - Even Relation

競技プログラミング

ぼくがかんがえたさいきょうの生活習慣を送っているえぬわいです。3 日だけですけど。これから続けていくんだという気持ち。

qiita.com

続きです。

atcoder.jp

ARC 036 D 偶数メートルのとっかかりの部分みたいな感じでした。たまたま偶数メートルの解説を読んだので、その知識を使ったら解法がすぐに見つかりました。

ポイントとしては、

  • 重さは、偶数、奇数で、場合分けして、すべての辺を重さ 1 として、重さの概念をなくす。
  • 塗ってみる

という感じです。

重さが偶数の辺が入った時は、間に無駄な頂点を追加して、その頂点を挟んで、重さ 1 の辺でつなぐことにする。重さが奇数の時は、そのまま、重さ 1 の辺にする。ここから 2 色で塗っていくと、すでに彩色されている。2部グラフの判定と多分同じ計算量だから、O(|E|+|V|)でO(2N)でO(N)になるのかな？

偶数になる理由として、頂点を増やした後のグラフについて、どの同じ色の頂点の組も間にある辺の数は常に偶数になっているからというのがあげられる。辺の重さは、1 としているから、辺の数=距離となる。

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

G = defaultdict(list)

N = int(input())
C = [0 for i in range(N)]
last = N


def rec(pos, c):
    """ 2 色で塗ることができることが保証されている """
    global C
    C[pos] = c
    for to in G[pos]:
        if C[to] == 0:
            rec(to, -c)


for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    # 無向グラフ
    if w%2 == 0:
        G[u].append(last)
        G[last].append(u)
        G[v].append(last)
        G[last].append(v)
        C.append(0)
        last += 1
    else:
        G[u].append(v)
        G[v].append(u)
rec(0, 1)
for i in range(N):
    print(0 if C[i] == -1 else 1)