水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ATC 001 B - Union Find(2015/06/06)

問題

Submission #421264 - AtCoder Typical Contest 001 | AtCoder

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

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")