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
考え方は合ってるようだし今日はここまで