徒然weed

アウトプットの場

ゆる〜くpythonの練習「互いに素な集合編」

f:id:shintaro-football7:20191022195746p:plain
今回はグループ分けについてです。
問題はこちら(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A)。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

ポイントは与えられたのノードの「ルート(根)」を調べてそれらが一致すれば同グループと判定すること。また、グループの結合(ここでは"unite(x,y)"としている)はそれぞれのルートを調べて異なっていたらどっちかのルートをもう片方のルートにバイパスする、ということ。
ちなみにpythonの最大再帰処理回数はデフォルト値が1000なのでsysライブラリのsetrecursionlimitをつかう。

import sys
sys.setrecursionlimit(1000000)

info = list(map(int,input().split()))
n,q = info[0],info[1]

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

def getroot(x):
    if x == parent[x]:
        return x
    parent[x] = getroot(parent[x])
    return parent[x]
for i  in range(q):
    xy = list(map(int,input().split()))
    root1,root2 = getroot(xy[1]),getroot(xy[2])
    if xy[0] == 0:
        parent[root1] = root2
    else:
        if root1 == root2:
            print(1)
        else:
            print(0)

本日のおまけ
弘中アナも神田松之丞もどっちも好き。