アルゴリズム学習—白駿1717号:集合の表示

もんだいぶんせき

初期0からnの間の数字がそれぞれn+1個の集合である場合に2種類の演算

を行う.
1)集約演算-0 ab形式で与える
2)2つの要素が同じ集合内に-1 a bの形で含まれていることを確認する.

問題であれば、集合を使用して直接演算できますが、各集合がルートを知らない可能性があるのでunion-paindを使用します.

1)集合がユニオン統一環節点に対応する
2)同一の集合の有無はパイプに対応し,コーナーポイントが異なる場合はNO,YESである.

アルゴリズムコード

には多くのタイムアウトの問題が発生し、2つの問題が解決された.

1) sys.setrecursionlimit(1000000)の設定
2)find関数をparent[x]=find parent(parent[x])に変更

2番の事項は私が間違っているかもしれません.

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())

parent = [i for i in range(n+1)]

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union(x, y):
    x = find_parent(x)
    y = find_parent(y)

    if x < y:
        parent[y] = x
    else:
        parent[x] = y

for _ in range(m):
    calculate, x, y = map(int, input().split())

    if calculate == 0:
        union(x, y)
    else:
        root_x = find_parent(x)
        root_y = find_parent(y)

        if root_x == root_y:
            print("YES")
        else:
            print("NO")