ARC036 D問題

AtCoder Regular ContestのD問題を解いた。
問題はこれ
D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder。
解説はこれ
AtCoder Regular Contest 036 解説。
書いてみたら、最後のテストケースだけREになって、なんでや！ってなって、調べた。
あった。
蟻本初級編攻略 - 2-4 Union Find木 後編 - Arantium Maestum
これによると、union-findで無限ループに陥ることがあるらしい。
この修正は、感覚的には、木treeの辺に向きがあると思って、その向きを数の大きい方が小さい方に揃えるイメージ。
そうすると、サイクルができない。

def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
##    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)

    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    A[y] = bx
    A[by] = bx

N, Q = map( int, input().split())
V = [ i for i in range(2*N)]
for _ in range(Q):
    w, x, y, z = map( int, input().split())
    x, y = x-1, y-1
    if w == 1:
        if z%2 == 0:
            union(V,x,y)
            union(V,x+N,y+N)
        else:
            union(V,x,y+N)
            union(V,y,x+N)
    else:
        if find(V,x) == find(V,y):
            print('YES')
        else:
            print('NO')

おまけ

##のsortedを使うより、if文で書いたほうが倍ぐらい速かった。
関数を呼び出さないほうが速いっぽい。
defも然り。