kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

DSL_1_A:Disjoint Set: Union Find Tree

互いに素な集合を結合したり、ふたつの要素が同じ集合に属しているかを判定したりする
Treeっていうくらいだし、ヒントの絵も木っぽいから木を使うんだろうな

この問題のちょっと変わってるところは、
集合を指定してそこにどんな要素が含まれているか、ということではなくて
まず要素があって、その要素を含む集合をどうこうする、ってとこだな

だから、集合から要素を探すより、要素から集合を探せたほうがよさそうだ
逆はできなくても解けそう
木になるしヒントの図にもだいたい合う(ちょっと合わないのが気になる

こんな感じかな
意外と単純じゃない?

class DisjointSet():
    def __init__(self):
        self.parent = None

def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s

def unite(elems, x, y):
    parent = DisjointSet()
    ancestor(elems, x).parent = parent
    ancestor(elems, y).parent = parent

def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)

def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)

if __name__ == '__main__':
    main()

だめでした
Case #2で早くもTLEになっている
これはなにか無限ループしているな
しかしなんで?

あー
unite済みの要素をさらにuniteするとおかしくなるな
考慮漏れだった

まずuniteされてないかどうかチェックしてからかな
こんな感じ

def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent

10000要素で50000コマンドまではいけたけど
70000コマンド(#31)でTLE
考え方は合ってるようだし今日はここまで