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

1251 ワード
python algorithm テキストリンク

もんだいぶんせき

  • 初期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")
    Section 6
    TreeSetの使用:一連の数の異なる数を取得(ソート)