Problem:


Disjoint Set

Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.

First of all, the program should read an integer n, then make a disjoint set where each element consists of 0, 1, ... n&minus;1 respectively.

Next, the program should read an integer q and manipulate the set for q queries. There are two kinds of queries for different operations:

unite(x, y): unites sets that contain x and y, say Sx and Sy, into a new set.

same(x, y): determine whether x and y are in the same set.

Input

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

In the first line, n and q are given. Then, q queries are given where com represents the type of queries. '0' denotes unite and '1' denotes same operation. 

Output

For each same operation, print 1 if x and y are in the same set, otherwise 0, in a line.

Constraints

1 ≤ n ≤ 10000

1 ≤ q ≤ 100000

x &ne; y

Sample Input

5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0

Sample Output

0
0
1
1
1
0
1
1



Sample input:
5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0


Sample output:
0
0
1
1
1
0
1
1

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    uf = UnionFind(N)
    for q in range(Q):
        com, x, y = il()
        if com == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # 0, 1, ..., n - 1を要素とするn個の集合
    def __init__(self, n):
        self.rank = [0] * n # 木の根のみが持つ値
        self.par = list(range(n))

    # 木の根を求める
    def find(self, x):
        children = []
        while self.par[x] != x:
            children.append(x)
            x = self.par[x]

        for c in children:
            self.par[c] = x
        return x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        if self.same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] > self.rank[ry]:
            self.par[ry] = rx # yの根をxの根の子とする。
        elif self.rank[rx] == self.rank[ry]:
            self.par[ry] = rx
            self.rank[rx] += 1
        else:
            self.par[rx] = ry

n, q = [int(x) for x in input().split()]
uf = UnionFind(n)

for _ in range(q):
    cmd, x, y = [int(x) for x in input().split()]
    if cmd == 0: # unite
        uf.union(x, y)
    else: # same
        print(int(uf.same(x, y)))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

from collections import defaultdict

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

dic = defaultdict()









def getRoot(x):
    global n
    for _ in range(n+1):
        if dic[x]["parent"] == x:
            return x
        x = dic[x]["parent"]

def makeSet(x):
    return


def unite(x, y):
    r = getRoot(x)
    l = getRoot(y)
    a = dic[r]["rank"]
    b = dic[l]["rank"]

    if a == b:
        dic[r]["rank"] += 1
        dic[l]["parent"] = r

    elif a > b:
        dic[l]["rank"] = 0
        dic[l]["parent"] = r

    elif a < b:
        dic[r]["rank"] = 0
        dic[r]["parent"] = l

for _ in range(n):
    dic[_] = {"rank":0,"parent":_}

for _ in range(q):
    com , x, y = map(int, input().split())
    if com == 0:
        unite(x, y)

    else:
        s = getRoot(x)
        t = getRoot(y)
        if s == t :
            print('1')
        else:
            print('0')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,q=map(int,input().split())
pair=[i for i in range(n)]

def root(x):
    if pair[x]==x:
        return x
    else:
        pair[x]=root(pair[x])
        return pair[x]

for i in range(q):
    com,x,y=map(int,input().split())
    if com==0:
        x1=root(x-1)
        y1=root(y-1)
        if x1!=y1:
            pair[x1]=y1
    elif com==1:
        if root(x-1)==root(y-1):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
        
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
            
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
                
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return 1
    else:
      return 0

n, q = map(int, input().split())
uf = UnionFind(n)
for i in range(q):
  a, b, c = map(int, input().split())
  if(a == 0):
    uf.unite(b, c)
  else:
    print(uf.is_in_group(b, c))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.parent = [-1] * N  

    def findset(self, A):  
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.findset(self.parent[A])  
        return self.parent[A]

    def size(self, A):  
        return -self.parent[self.findset(A)]

    def unite(self, A, B):
        A = self.findset(A)
        B = self.findset(B)

        if (A == B):
            return False

        if (self.size(A) < self.size(B)):
            A, B = B, A

        self.parent[A] += self.parent[B]  
        self.parent[B] = A  

        return True

    def is_in_same(self, A, B):
        return self.findset(A) == self.findset(B)


N, Q = map(int, input().split())
ds = UnionFind(N)
for q in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        ds.unite(x, y)
    elif com == 1:

        print(1 if ds.is_in_same(x, y) else 0)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, Q = map(int, input().split())
    uf = UnionFind(N)

    for _ in range(Q):
        query, x, y = map(int, input().split())
        if query == 0:
            uf.union(x, y)
        else:
            if uf.same(x, y):
                print('1')
            else:
                print('0')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


n, q = map(int, input().split())
par = [-1] * n

for i in range(q):
    j, x, y = map(int, input().split())
    if j == 0:
        unite(x, y)
    else:
        print(1 if same(x, y) else 0)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.p = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    def link(self,x,y):
        if self.rank[x]>self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x]==self.rank[y]:
                self.rank[y] += 1
                
    def find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
        
n,q = map(int,input().split())
djs = DisjointSet(n)

for i in range(q):
    com,x,y = map(int,input().split())
    if com == 0:
        djs.unite(x,y)
    else:
        print(int(djs.same(x,y)))

Submission status: Accepted

Solution code:
(n,q), *cxy = [list(map(int, s.split())) for s in open(0)]

class UnionFind:
    def __init__(self, n):
        self.parent = {i:i for i in range(n)}
        
    def find_root(self, x):
        parent = self.parent[x]
        if x != parent:
            result = self.find_root(parent)
            self.parent[x] = result
            return result
        else:
            return x

    def unite(self, x, y):
        if x == y:
            return
        
        x, y = min(x,y), max(x,y)
        x = self.find_root(x)
        y = self.find_root(y)
        
        if x == y:
            return
        elif x > y:
            x = self.find_root(x)
            if x == y:
                return
            x, y = min(x,y), max(x,y)
        self.parent[y] = x

    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

u = UnionFind(n)

for c,x,y in cxy:
    if c:
        print(int(u.same(x,y)))
    else:
        u.unite(x,y)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A

n, q = list(map(int, input().split()))
parents = [-1 for _ in range(n)]


def root(i):
    if parents[i] == -1:
        return i
    else:
        parents[i] = root(parents[i])
        return parents[i]


def unite(x, y):
    if same(x, y):
        return

    x = root(x)
    y = root(y)
    parents[y] = x


def same(x, y):
    return root(x) == root(y)


for _ in range(q):
    com, x, y = list(map(int, input().split()))
    if com == 0:
        unite(x, y)
    elif com == 1:
        if same(x, y):
            print(1)
        else:
            print(0)
    else:
        raise Exception

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=ja

# union-find

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

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1] * n


for _ in range(q):
    com, ai, bi = map(int, input().split())
    # ai, bi = ai - 1, bi - 1

    # com = 0 (unite) / 1 (same)
    if com == 0:
        unite(ai, bi)
    else:
        print(1 if same(ai, bi) else 0)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())

#Union-Find木の構築
par=[-1]*n

def find(v):
    if par[v]<0:
        return v
    else:
        par[v]=find(par[v])
        return par[v]

def union(u,v):
    root_u=find(u)
    root_v=find(v)

    if root_u==root_v:
        return 
    
    #大きい方に接続
    if par[root_u]>par[root_v]:
        par[root_v]+=par[root_u]
        par[root_u]=root_v
    else:
        par[root_u]+=par[root_v]
        par[root_v]=root_u

def same(u,v):
    if find(u)==find(v):
        return True
    else:
        return False

for i in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        union(x,y)
    else:
        ans=same(x,y)
        if ans:
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x


def main():
    n, q = map(int, input().split())
    union_find = UnionFindTree(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            union_find.union(x, y)
        else:
            x_p = union_find.find(x)
            y_p = union_find.find(y)
            if x_p == y_p:
                print(1)
            else:
                print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親が同じか判別する
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            uf.union(x, y)
        else:
            print(1 if uf.same(x, y) else 0)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
n,q=map(int,input().split())
uf=UnionFind(n)
for _ in range(q):
  a,b,c=map(int,input().split())
  if a:print(int(uf.isSameGroup(b,c)))
  else:uf.Unite(b,c)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,q = map(int,input().split())
uf = UnionFind(n)
for _ in range(q):
    a,x,y = map(int,input().split())
    if a:
        print(int(uf.same(x,y)))
    else:
        uf.union(x,y)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [-1] * N

  def find(self, n):
    if self.parents[n] < 0:
      return n
    else:
      self.parents[n] = self.find(self.parents[n])
      return self.parents[n]

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

n,q = map(int,input().split())
uf = UF(n)
for _ in range(q):
  i,u,v = map(int,input().split())
  if i==0:
    uf.union(u,v)
  else:
    if uf.same(u,v):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)


n, q = map(int,input().split())
uf = UnionFind(n)
for q in range(q):
    cmd, i, j = map(int,input().split())
    if cmd == 0:
        uf.unite(i,j)
    else:
        print(int(uf.same(i,j)))

Submission status: Accepted

Solution code:
# DSL_1_A.py
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, Q = map(int, input().split())
union_find = UnionFind(N)
for i in range(Q):
    query, x, y = map(int, input().split())
    x = int(x)
    y = int(y)
    if query == 0:
        union_find.union(x, y)
    else:
        print(1 if union_find.same(x, y) else 0)

Submission status: Accepted

Solution code:
class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)

def main():
    n,q = map(int,input().split())
    uf = UF(n)
    for _ in range(q):
        ope,x,y = map(int,input().split())
        if ope == 0:
            uf.union(x,y)
        else:
            print(1 if uf.is_same(x,y) else 0)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [x for x in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[y] > self.rank[x]:
            self.par[x] = y
        else:
            self.par[x] = y
            self.rank[y] += 1
    
    def same(self, x, y):
        return (self.find(x) == self.find(y))

n, q = map(int, input().split())
uf = UnionFind(n)
for i in range(q):
    _c, _x, _y = map(int, input().split())
    if _c == 0:
        uf.unite(_x, _y)
    else:
        if uf.same(_x, _y):
            print("1")
        else:
            print("0")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

    def same(self, x, y):
        px = self.root(x); py = self.root(y)
        return px == py

n,q = list(map(int,input().split()))
COMXY = [list(map(int,input().split())) for _ in range(q)]
union_find = UnionFind(n)
for comxy in COMXY:
    if comxy[0] == 0:
        union_find.unite(comxy[1],comxy[2])
    if comxy[0] == 1:
        if union_find.same(comxy[1],comxy[2]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000)

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

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        par[rx] = ry

def same(x, y):
    return root(x) == root(y)

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

for i in range(q):
    p, a, b = map(int, input().split())
    if p:
        print(1 if same(a, b) else 0)
    else:
        unite(a, b)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

u = UnionFind(n)
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        u.unite(x, y)
    else:
        print(1 if u.is_same(x, y) else 0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):#要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):#要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
 
    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):#すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):#グループの数を返す
        return len(self.roots())
 
    def all_group_members(self):#{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):#print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(n)

for i in range(q):
    query = list(map(int,input().split()))
    if query[0] == 0:
        uf.union(query[1], query[2])
    else:
        print(int(uf.same(query[1], query[2])))

Submission status: Accepted

Solution code:
N, Q = map(int,input().split())
P = [i for i in range(N)]

def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x

def is_same_set(x,y):
    return root(x) == root(y)

def unite(x,y):
    P[root(x)] = root(y)
    
for _ in range(Q):
    com,x,y = map(int,input().split())
    if com == 0:
        unite(x,y)
    elif com == 1:
        if is_same_set(x,y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
P=[i for i in range(n)]
def root(x):
  path_to_root = []
  while P[x] != x:
    path_to_root.append(x)
    x = P[x]
  for node in path_to_root:
    P[node] = x
  return x
def same(x,y):
  return root(x) == root(y)
def unite(x,y):
  P[root(x)] = root(y)
for i in range(q):
  t,x,y=map(int,input().split())
  if t==0: unite(x,y)
  else: print('1' if same(x,y) else '0')

Submission status: Accepted

Solution code:
n, q = map(int, input().split())

tree = [i for i in range(n)]
def root(x):
    pre = []
    while x != tree[x]:
        pre.append(x)
        x = tree[x]
    for node in pre:
        tree[node] = x
    return x
def unite(x, y):
    X, Y = root(x), root(y)
    if X != Y:
        tree[X] = Y
def same(x, y):
    if root(x) == root(y):
        return print(1)
    else:
        return print(0)

for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        unite(x, y)
    else:
        same(x, y)

Submission status: Accepted

Solution code:
N,Q = map(int,input().strip().split())
P = [i for i in range(N)]
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x # パス圧縮
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)
for i in range(Q):
    q,x,y = map(int,input().strip().split())
    if q == 0:
        unite(x,y)
    if q == 1:
        print(int(is_same_set(x,y)))