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:
class UnionSet:
    def __init__(self, nmax: int) -> None:
        self.size = [1] * nmax
        self.id = [i for i in range(nmax)]

    def root(self, i: int) -> int:
        while (i != self.id[i]):
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def connected(self, p: int, q: int) -> bool:
        return self.root(p) == self.root(q)

    def unite(self, p: int, q: int) -> None:
        i, j = self.root(p), self.root(q)
        if (i == j):
            return
        if self.size[i] < self.size[j]:
            self.id[i] = j
            self.size[j] += self.size[i]
        else:
            self.id[j] = i
            self.size[i] += self.size[j]


if __name__ == "__main__":
    n, q = map(int, input().split())

    u = UnionSet(n)
    for _ in range(q):
        op, x, y = map(lambda x: int(x), input().split())
        if (0 == op):
            u.unite(x, y)
        else:
            print(f"{1 if u.connected(x, y) else 0}")

Submission status: Accepted

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

class Union_find:
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):# 頂点xのroot(根)頂点を見つける
        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と頂点yを繋ぐ辺を追加
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def same(self,x,y):#頂点xと頂点yが連結であるか判定
        return self.find_root(x)==self.find_root(y)

    def count(self,x):#頂点xが属する木のサイズ
        return -self.root[self.find_root(x)]

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

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n

    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))

    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]


def main():
    n, q = map(int, input().split())
    ds = DisjointSet(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            ds.unite(x, y)
        elif com == 1:
            print(1 if ds.same(x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, data):
        self.data = data
        self.parent = self

def find_root(node):
    if node.parent == node:
        return node

    else:
        node.parent = find_root(node.parent)
        return node.parent

def unite(x, y):
    x_root = find_root(x)
    y_root = find_root(y)
    if x_root == y_root:
        return
    else:
        y_root.parent = x_root

def same(x, y):
    if find_root(x) == find_root(y):
        print(1)
    else:
        print(0)


if __name__ == '__main__':
    n, q = map(int, input().split())

    nodeset = []
    for i in range(n):
        nodeset.append(Node(i))

    for i in range(q):  
        com, x, y = map(int, input().split())
        x_node = nodeset[x]
        y_node = nodeset[y]
        if com == 0:
            unite(x_node, y_node)
        else:
            same(x_node, y_node)

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)
l=[list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    p,x,y=l[i][0],l[i][1],l[i][2]
    if not p:
        uf.Unite(x,y)
    else:
        print(1 if uf.isSameGroup(x,y) else 0)

Submission status: Accepted

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

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:  #unite
        uf.union(x, y)
    elif com == 1:  # same
        if uf.same_check(x, y):
            print('1')
        else:
            print('0')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


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

  def root(self, i):
    if i != self.parent[i]:
      self.parent[i] = self.root(self.parent[i])
    return self.parent[i]

  def union(self, i, j):
    pi, pj = self.root(i), self.root(j)
    if pi == pj:
      return
    if self.height[pi] < self.height[pj]:
      self.parent[pi] = pj
      self.size[pj] += self.size[pi]
    else:
      self.parent[pj] = pi
      self.size[pi] += self.size[pj]
      if self.height[pi] == self.height[pj]:
        self.height[pi] += 1

  def is_same(self, i, j):
    return self.root(i) == self.root(j)


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


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    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 findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

if __name__ == '__main__':
    n, q = map(int, input().split())
    ds = DisjointSet(n)    
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            ds.unite(x, y)
        else:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()
n,q=map(int,input().split())
U=[UnionFindNode(i) for i in range(n)]
for i in range(q):
    com,x,y=map(int,input().split())
    x-=1
    y-=1
    if com==0:
        U[x].unite(U[y])
    else:
        if U[x].is_group(U[y]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


class Node:
    
    def __init__(self):
        self.root = self
        self.child = None
        self.length = 1
    
    def set_root(self, root):
        if self.child:
            self.child.set_root(root)
        self.root = root
            
    def set_child(self, child):
        if self.child:
            self.child.set_child(child)
        else:
            self.child = child
        
        
n,q = [int(i) for i in input().split()]
A = []
for i in range(n):
    A.append(Node())

for i in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        if A[x].root == A[y].root:
            continue
        if A[x].root.length < A[y].root.length:
            A[y].set_child(A[x].root)
            A[y].root.length += A[x].root.length
            A[x].root.set_root(A[y].root)
        else:
            A[x].set_child(A[y].root)
            A[x].root.length += A[y].root.length
            A[y].root.set_root(A[x].root)
    else:
        if A[x].root == A[y].root:
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
def find(x):
    global s
    if s[x] == x:
        return x
    s[x] = find(s[x])
    return s[x]
 
n, q = map(int, input().split())
 
s =[i for i in range(n)]
 
for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if find(x) == find(y): print(1)
        else: print(0)
    else:
        s[find(y)] = find(x)

Submission status: Accepted

Solution code:
n, q = map(int,input().split())
queries = []
for _ in range(q):
    com, x, y = map(int,input().split())
    queries.append((com, x, y))

joining = [[x] for x in range(n)]

def unite(x, y):
    if joining[x] == joining[y]:
        return
    joining[x] += joining[y]
    for member in joining[y]:
        joining[member] = joining[x]

def is_same(x, y):
    return joining[x] == joining[y]

answers = []
for query in queries:
    if query[0] == 0:
        unite(query[1], query[2])
    else:
        answers.append(is_same(query[1], query[2]))

for answer in answers:
    if answer:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
def main():
     def root(x):
          path=[]
          while x!=P[x]:
               path.append(x)
               x=P[x]
          for i in path:
               P[i]=x
          return x
     
     def is_same_set(x,y):
          return root(x)==root(y)
     
     def unite(x,y):
          P[root(x)]=root(y)
     
     n,q=map(int,input().split())
     P=[i for i in range(n)]
     for i in range(q):
          q,a,b=map(int,input().split())
          if q==0:
               unite(a,b)
          else:
               if is_same_set(a,b):
                    print(1)
               else:
                    print(0)
     
if __name__=='__main__':
     main()

Submission status: Accepted

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

def unite(x,y):
    P[root(x)] = root(y)

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

n,q = map(int,input().split())
P = [i for i in range(n)]
for _ in range(q):
    com,x,y=map(int,input().split())
    if com == 0:
        unite(x,y)
    else:
        if is_same_set(x,y):
            print(1)
        else:
            print(0)

Submission status: Accepted

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

uf = list(range(n))
import sys
sys.setrecursionlimit(30000)
def find_root(x):
    global uf
    if uf[x] == x:
        return x
    else:
        uf[x] = find_root(uf[x])
        return uf[x]

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
L = []
for i in range(q):
    L.append(list(map(int,input().split())))
par = []
for i in range(n):
    par.append(i)
rank = [0]*n
def find(x,par):
    if x == par[x]:
        return x
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
for i in range(q):
    if L[i][0] == 0:
        unite(L[i][1],L[i][2],par,rank)
    else:
        if find(L[i][1],par) == find(L[i][2],par):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
def root(x):
    path = []
    while P[x] != x:
        path.append(x)
        x = P[x]
    for node in path:
        P[node] = x
    return x
def check(x,y):
    if root(x) == root(y):
        return 1
    else:
        return 0
def unite(x,y):
    P[root(x)] = root(y)        
 
n,q = map(int,input().split())
P = [i for i in range(n)]
for j in range(q):
    s = list(map(int,input().split()))
    if s[0] == 0:
        unite(s[1],s[2])
    else:
        print(check(s[1],s[2]))
    #print(P)

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):
    if root(x) == root(y):
        return 1
    else: return 0
def unite(x,y):
    P[root(x)] = root(y)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[i for i in range(n+1)]
def root(n):
  pathroot=[]
  while p[n]!=n:
    pathroot.append(n)
    n=p[n]
  for node in pathroot:
    p[node]=n
  return n
def same(n,m):
  return root(p[n])==root(p[m])
def union(n,m):
  p[root(n)]=root(m)
for i in range(m):
  a,x,y=map(int,input().split())
  if a==1:
    if same(x,y):
      print(1)
    else:
      print(0)
  else:
    union(x,y)

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

for _ in range(q):
    com,x,y=map(int,input().split())
    if com:
        print(int(root(x)==root(y)))
    else:
        p[root(x)]=root(y)

Submission status: Accepted

Solution code:
def root(x):
    path = []
    while P[x] != x:
        path.append(x)
        x = P[x]
    for node in path:
        P[node] = x
    return x
def check(x,y):
    if root(x) == root(y):
        return 1
    else:
        return 0
def unite(x,y):
    P[root(x)] = root(y)        

n,q = map(int,input().split())
P = [i for i in range(n)]
for j in range(q):
    s = list(map(int,input().split()))
    if s[0] == 0:
        unite(s[1],s[2])
    else:
        print(check(s[1],s[2]))
    #print(P)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, dimension):
        self.root = [i for i in range(dimension)]
        self.height = [1 for i in range(dimension)]

    def parent(self, i):
        p = self.root[i]
        if i == p:
            return p
        else:
            pp = self.parent(p)
            self.root[i] = pp
            return pp

    def unite(self, i1, i2):
        p1 = self.parent(i1)
        p2 = self.parent(i2)
        if self.height[p1] < self.height[p2]:
            self.root[p1] = p2
        else:
            self.root[p2] = p1
            if self.height[p1] == self.height[p2]:
                self.height[p1] += 1

    def same(self, i1, i2):
        return self.parent(i1) == self.parent(i2)


n, q = map(int, input().strip().split())
uf = UnionFind(n)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

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.is_connected(x, y) else 0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

par = [i for i in range(n + 1)]
rnk = [0 for i in range(n + 1)]

def find(x):
    if par[x] == x:
        return x
    par[x] = find(par[x])
    return par[x]

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

def unite(x, y):
    x_par = find(x)
    y_par = find(y)
    if x_par == y_par:
        return
    
    if rnk[x_par] < rnk[y_par]:
        par[x_par] = y_par
    else:
        par[y_par] = x_par
        if rnk[x_par] == rnk[y_par]:
            rnk[x_par] += 1

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

Submission status: Accepted

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

n,q = [int(s) for s in input().split()]
par = []
for i in range(n):
    par.append(i)

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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

for i in range(q):
    q_type,x,y = [int(s) for s in input().split()]
    if q_type == 1:
        if same(x,y):
            print(1)
        else:
            print(0)
    else:
        union(x,y)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in read(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    sys.setrecursionlimit(100000)
    n, q = readi(2)
    par = arr(n + 1)
    for i in range(len(par)):
        par[i] = i

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

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        par[x] = y

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

    for _ in range(q):
        com, x, y = readi(3)
        if com == 0:
            unite(x, y)
        else:
            print(1 if same(x, y) else 0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import Union, List
import sys

sys.setrecursionlimit(100000)

# 木の根を返す
def find(x: int, S: List[int]) -> int:
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]

# xとyが同じ集合に属すかの判定
def same(x: int, y: int, S: List[int]) -> bool:
    return find(x, S) == find(y, S)

# xとyの属する集合を結合
def unite(x: int, y: int, S: List[int]) -> None:
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [n, q] = [int(i) for i in input().split()]

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

    for i in range(q):
        [com, x, y] = [int(i) for i in input().split()]
        if com == 0:
            unite(x, y, S)
        elif com == 1:
            if same(x, y, S):
                print('1')
            else:
                print('0')
        else:
            raise ValueError('value error')

Submission status: Accepted

Solution code:
#union-find-tree
import sys
sys.setrecursionlimit(10**7)
def init(n):
    return list(range(n+1))
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

n, q = map(int, input().split())
union_find_lis = init(n-1)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        union(union_find_lis, x, y)
    else:
        if sameset(union_find_lis, x, y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UF:
  def __init__(self,n):
    self.n = n
    self.p = [i for i in range(n)]
    self.r = [1]*n
    self.num = n
  
  def find(self,x):
    if x == self.p[x]:
      return x
    self.p[x] = UF.find(self,self.p[x])
    return self.p[x]
  
  def same(self,x,y):
    return UF.find(self,x) == UF.find(self,y)
  
  def unite(self,x,y):
    x = UF.find(self,x)
    y = UF.find(self,y)
    if x == y:
      return
    if self.r[x] < self.r[y]:
      x,y = y,x
    self.r[x] += self.r[y]
    self.p[y] = x
    self.num -= 1

  def size(self,x):
    return self.r[x]
  
  def count(self):
    return self.num

[n,q] = list(map(int,input().split()))
uf = UF(n)
for i in range(q):
  [com,x,y] = list(map(int,input().split()))
  x -= 1
  y -= 1
  if com == 0:
    uf.unite(x,y)
  else:
    if uf.same(x,y):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
import sys

class UnionFind(object):
    def __init__(self):
        self.node_id = {}
        self.parent_id = []
        self.rank = []

    def find(self, node_id):
        while node_id != self.parent_id[node_id]:
            pp = self.parent_id[self.parent_id[node_id]]
            self.parent_id[node_id] = pp
            node_id = pp
        return node_id

    def add(self, x):
        if x in self.node_id:
            return self.node_id[x]
        node_id = len(self.node_id)
        self.node_id[x] = node_id
        self.parent_id.append(len(self.parent_id))
        self.rank.append(0)
        return node_id

    def union(self, p, q):
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent_id[i] = j
        elif self.rank[i] > self.rank[j]:
            self.parent_id[j] = i
        else:
            self.parent_id[j] = i
            self.rank[i] += 1

    def dump_groups(self):
        result = []
        group_id = {}
        for x, i in self.node_id.items():
            j = self.find(i)
            if j not in group_id:
                group_id[j] = len(result)
                result.append([])
            result[group_id[j]].append(x)
        return result

    def dump_dot(self):
        result = """digraph { graph [rankdir=LR];\n"""
        for i, target in enumerate(self.parent_id):
            result += """"%s" [label=\"%s\",shape=plaintext,shape=circle];\n""" % (i, i)
            if i != target:
                result += """"%s" -> "%s";\n""" % (i, target)
        result += "}"
        return result

uf = UnionFind()
(n, q) = sys.stdin.readline().split()
for i in range(int(n)):
    uf.add(i)
for i in range(int(q)):
    (c, x, y) = sys.stdin.readline().split()
    if c == "0":
        uf.union(int(x), int(y))
    else:
        print(1 if uf.find(int(x)) == uf.find(int(y)) else 0)

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.siz = [1] * (n+1)

    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 same_checker(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.siz[y] += self.siz[x]
        else:
            self.par[y] = x
            self.siz[x] += self.siz[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        return self.siz[self.find(x)]
        
n, q = map(int, input().split())
union_find_tree = Union_Find(n)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        union_find_tree.union(x, y)
    else:
        if union_find_tree.same_checker(x, y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def root(s):
    global pa
    if pa[s] == s:
        return s
    pa[s] = p = root(pa[s])
    return p

def unite(s, t):
    global pa
    a = root(s);b = root(t)
    if a == b:
        return 1
    elif rank[a] == rank[b]:
        pa[b] = a
        rank[a] += 1
    else:
        if rank[a] < rank[b]:
            pa[a] = b
        else:
            pa[b] = a

n, q = map(int, input().split())
pa = [i for i in range(n)]
rank = [1]*n
for i in range(q):
    a, b, c = map(int, input().split())
    if a == 0:unite(b,c)
    else:
        if root(b) == root(c):
            print(1)
        else:print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def findSet(x):
  if x == parent[x]:
    return x
  else:
    return findSet(parent[x])

def link(x, y):
  if rank[x] < rank[y]:
    parent[x] = y
  else:
    parent[y] = x
    if rank[x] == rank[y]:
      rank[y] += 1

def union(x, y):
  link(findSet(x), findSet(y))

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

data = (i for i in range(n))
rank = [0 for i in range(n)]
parent = [i for i in range(n)]

for i in range(q):
  f, x, y = list(map(int, input().split()))
  if f == 0:
    union(x, y)
  else:
    if findSet(x) == findSet(y):
      print(1)
    else:
      print(0)