ATC 001 B - Union Find（2015/06/06）

問題

B: Union Find - AtCoder Typical Contest 001 | AtCoder

問題

Submission #421264 - AtCoder Typical Contest 001 | AtCoder

アルゴリズムの解説はもうスライド見てくださいっていう（

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

こっちの方はPythonでもうまく行ったので，特に無いですね．
ただし本番ではfindメソッド経路圧縮の関係か，最初テーブルの中身を直接比較するisSameメソッドでの処理でREが発生しました．
ちゃんとfindメソッド使って経路圧縮して比較しましょう．

N, Q = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]
 
unilist = [i for i in range(N)]
 
def find(x):
    if x == unilist[x]:
        return x
    else:
        unilist[x] = find(unilist[x])
        return unilist[x]
 
def union(x, y):
    s1, s2 = find(x), find(y)
    if s1 != s2:
        unilist[s2] = s1
 
def isSame(x, y):
    return find(x) == find(y)
 
for query in queries:
    if query[0] == 0:
        union(query[1], query[2])
    else:
        print("Yes" if isSame(query[1], query[2]) else "No")