ARC 036 D 偶数メートル - いろんなことで四苦Hack（仮）

続き。

ARC D だけあって解答の読み応えがちげぇぜ(解答見た)

UnionFindを使うと、状態管理をすることができる例。

UnionFindで N 個の頂点間を偶数距離で移動できるかの判定に使っている。解答みておったまげた。

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x); y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
        else:
            self.rank[y] += 1
            self.par[x] = y

N, Q = map(int, input().split())
uf = UnionFind(2*N)
for i in range(Q):
    w, x, y, z = map(int, input().split())
    if w == 1:
        if z%2 == 0:
            # 青
            uf.unite(2*(x-1), 2*(y-1))
            # 赤
            uf.unite(2*(x-1)+1, 2*(y-1)+1)
        else:
            uf.unite(2*(x-1), 2*(y-1)+1)
            uf.unite(2*(x-1)+1, 2*(y-1))
    else:
        if uf.find(2*(x-1)+1) == uf.find(2*(y-1)+1):
            print('YES')
        else:
            print('NO')

問題の解答の一番最後に載ってた。基本的に、2 部グラフから考察を重ねるのが、勉強しがいのあるやり方みたいだ。

同じ頂点番号の頂点を 2 つずつ用意して、青、赤に分けておく。もし、道路ができる時、距離が偶数なら、その同じ色同士を結ぶ。偶数じゃなかったら、別の色同士を結ぶ。最終的に、赤だけを見て、同じ連結成分なら、YES, 違かったらNOで判断できる。短すぎるだろ...

覚えておきたいテクニックだと思いました。