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

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.is_same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    def find_root(self, x):
        if x != self.root[x]:
            self.root[x] = self.find_root(self.root[x])

        return self.root[x]

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

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    ds = [[i] for i in range(n)]
    n2s = [i for i in range(n)]
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            merge(ds, n2s, x, y)
        else:
            ans.append(1 if n2s[x] == n2s[y] else 0)

    print(*ans, sep='\n')

def merge(ds, n2s, x, y):
    u = n2s[x]
    v = n2s[y]

    if u == v:
        return None

    if len(ds[u]) < len(ds[v]):
        ds[v].extend(ds[u])
        for w in ds[u]:
            n2s[w] = v
        del ds[u][:]
    else:
        ds[u].extend(ds[v])
        for w in ds[v]:
            n2s[w] = u
        del ds[v][:]

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    ds = [[i] for i in range(n)]
    n2s = [i for i in range(n)]
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            merge(ds, n2s, x, y)
        else:
            ans.append(1 if n2s[x] == n2s[y] else 0)

    print(*ans, sep='\n')

def merge(ds, n2s, x, y):
    u = n2s[x]
    v = n2s[y]

    if u == v:
        return None

    ds[v].extend(ds[u])
    for w in ds[u]:
        n2s[w] = v
    del ds[u][:]

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**5)

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.is_same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        # self.rank = [0] * n

    def find_root(self, x):
        if x != self.root[x]:
            self.root[x] = self.find_root(self.root[x])

        return self.root[x]

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

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)
        self.root[p] = q

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []
    
    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    def find_root(self, x):
        if self.root[x] == x:
            return x

        res = self.root[x]

        while res != self.root[res]:
            res = self.root[res]

        return res

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

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

"""Disjoint Set"""

import sys
import os
import pprint


class Node:
    def __init__(self, key):
        self.parent = self
        self.key = key
        self.rank = 0  # ???????????????????????¨????????¨????????¨?????????

    def get_root(self):
        """
        :rtype: Node
        :return:
        """
        n = self
        while n.parent is not n:
            n = n.parent
        return n


# ????????????????????????
def unite(x, y):
    node_x = nodes[x]
    node_y = nodes[y]

    root_x = node_x.get_root()
    root_y = node_y.get_root()

    if root_x.rank > root_y.rank:
        # root x???????????????
        root_y.parent = root_x
    elif node_x.rank == node_y.rank:
        # root x???????????????
        root_y.parent = root_x
        # root x?????????????????´
        root_x.rank += 1
    else:
        # node y?????????????????????
        root_x.parent = root_y

# ??£??¨??????????????????
def find_set(x):
    node = nodes[x]
    return node.get_root().key


#fd = os.open('DSL_1_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

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

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

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    if com == 0:
        # unite
        unite(x, y)
    else:
        # same
        id0 = find_set(x)
        id1 = find_set(y)
        if id0 == id1:
            print(1)
        else:
            print(0)



def node_test():
    node0 = Node(0)
    node1 = Node(1)
    node1.parent = node0
    node2 = Node(2)
    node2.parent = node1
    n = node2.get_root()
    print(n.key)
    print(node2.key)

if __name__ == '__main__':
    #node_test()
    pass

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent = {}
        for i in range(n):
            self.parent[i] = i

    def get_root(self,x):
        r = x
        depth = 0
        path = [r]
        while self.parent[r]!=r:
            r = self.parent[r]
            path.append(r)
            depth += 1
        for n in path:
            self.parent[n] = r
        return r,depth

    def unite(self,x,y):
        rx,dx = self.get_root(x)
        ry,dy = self.get_root(y)
        if rx!=ry:
            if dx > dy:
                self.parent[ry] = rx
            else:
                self.parent[rx] = ry

    def same(self,x,y):
        rx,_ = self.get_root(x)
        ry,_ = self.get_root(y)
        if rx==ry: return 1
        else: return 0


n,q = map(int,raw_input().split(' '))
tree = UnionFind(n)

answers = []
for _ in range(q):
    com,x,y = map(int,raw_input().split(' '))
    if com==0:
        tree.unite(x,y)
    elif com==1:
        answers.append(tree.same(x,y))

for a in answers:
    print a

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

output:
0
0
1
1
1
0
1
1
"""


class UnionFind(object):
    def __init__(self, size):
        self.size = size
        self.height_rank = [0] * self.size
        self.ancestors = list(range(self.size))

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

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

    def link(self, x, y):
        if self.height_rank[x] > self.height_rank[y]:
            self.ancestors[y] = x
        else:
            self.ancestors[x] = y
            if self.height_rank[x] == self.height_rank[y]:
                self.height_rank[y] += 1

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


if __name__ == '__main__':
    import sys
    input_ = sys.stdin.readlines()
    e_num, c_num = map(int, input_[0].split())
    cmds = map(lambda x: x.split(), input_[1:])
    case = UnionFind(size=e_num)
    for each in cmds:
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            print(int(case.same(ele_1, ele_2)))

Submission status: Accepted

Solution code:
def make_set(x, disjoint):
    disjoint[x] = x

def find_set(x, disjoint):
    if x not in disjoint.keys():
        make_set(x, disjoint)
    if x != disjoint[x]:
        disjoint[x] = find_set(disjoint[x], disjoint)
    return disjoint[x]

def link(x, y, disjoint):
    disjoint[y] = x

def unite(x, y, disjoint):
    link(find_set(x, disjoint), find_set(y, disjoint), disjoint)

def same(x, y, disjoint):
    if find_set(x, disjoint) == find_set(y, disjoint):
        return 1
    return 0

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

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

disjoint = dict()

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]

    if com == 0:
        unite(x, y, disjoint)
    else:
        print(same(x, y, disjoint))

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.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]

n,q = map(int, input().split())
ds = DisjointSet(n)
for i in range(q):
    t,a,b = map(int, input().split())
    if t == 0:
        ds.unite(a,b)
    elif t == 1:
        if ds.same(a,b):
            print("1")
        else:
            print("0")

Submission status: Accepted

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

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        print(int(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())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["forest"]

    def __init__(self, forest: list):
        self.forest = forest

    def get_root(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.get_root(self.forest[x])
            return self.forest[x]

    def unite(self, x, y) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.forest[root_x] < self.forest[root_y]\
                else (root_y, root_x)
            self.forest[bigroot] += self.forest[smallroot]
            self.forest[smallroot] = bigroot

n, q = map(int, input().split())
uf = UnionFind([-1 for _ in [None]*n])
for _ in [None]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        uf.unite(x, y)
    else:
        print(1 if uf.get_root(x) == uf.get_root(y) else 0)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
forest = [-1]*n


def get_root(x: int) -> int:
    if forest[x] < 0:
        return x
    else:
        forest[x] = get_root(forest[x])
        return forest[x]


def unite(x: int, y: int) -> None:
    root_x, root_y = get_root(x), get_root(y)
    if root_x != root_y:
        bigroot, smallroot = \
            (root_x, root_y) if forest[root_x] < forest[root_y]\
            else (root_y, root_x)
        forest[bigroot] += forest[smallroot]
        forest[smallroot] = bigroot

for _ in [None]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        unite(x, y)
    else:
        print(1 if get_root(x) == get_root(y) else 0)

Submission status: Accepted

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

*parent, = range(n)
def root(x):
    if x != parent[x]:
        x = parent[x] = root(parent[x])
    return x

def unite(x, y):
    px = root(x)
    py = root(y)

    if px < py:
        parent[py] = px
    else:
        parent[px] = py

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

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

Submission status: Accepted

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

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

*parent, = range(n)
def root(x):
    if x != parent[x]:
        x = parent[x] = root(parent[x])
    return x

def unite(x, y):
    px = root(x)
    py = root(y)

    if px < py:
        parent[py] = px
    else:
        parent[px] = py

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

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

Submission status: Accepted

Solution code:
from sys import stdin
high = [0] * 10000
par = [i for i in range(10000)]
def findSet(x):
    if par[x] == x: return x
    par[x] = findSet(par[x])
    return par[x]
def unite(x, y):
    x = findSet(x)
    y = findSet(y)
    if x == y: return
    if high[x] > high[y]: par[y] = x;
    else:
        par[x] = y
        if high[x] == high[y]: high[y] += 1
def same(x, y):
    return findSet(x) == findSet(y)
n, q = map(int, stdin.readline().split())
for i in range(q):
    t, a, b = map(int, stdin.readline().split())
    if t == 0: unite(a, b);
    elif t == 1: print(1 if same(a, b) else 0)

Submission status: Accepted

Solution code:
from sys import stdin
high = [0] * 10000
par = [i for i in range(10000)]
def findSet(x):
    if par[x] == x: return x
    par[x] = findSet(par[x])
    return par[x]
def unite(x, y):
    x = findSet(x)
    y = findSet(y)
    if x == y: return
    if high[x] > high[y]: par[y] = x;
    else:
        par[x] = y
        if high[x] == high[y]: high[y] += 1
def same(x, y):
    return findSet(x) == findSet(y)
n, q = map(int, stdin.readline().split())
ans = []
for i in range(q):
    t, a, b = map(int, stdin.readline().split())
    if t == 0: unite(a, b);
    elif t == 1: ans.append(1 if same(a, b) else 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin
high = [0] * 10000
par = [i for i in range(10000)]
def findSet(x):
    if par[x] == x: return x
    par[x] = findSet(par[x])
    return par[x]
def unite(x, y):
    x = findSet(x)
    y = findSet(y)
    if x == y: return
    if high[x] > high[y]: par[y] = x;
    else:
        par[x] = y
        if high[x] == high[y]: high[y] += 1
def same(x, y):
    return findSet(x) == findSet(y)
n, q = map(int, stdin.readline().split())
ans = []
ans_append = ans.append
for i in range(q):
    t, a, b = map(int, stdin.readline().split())
    if t == 0: unite(a, b);
    elif t == 1: ans_append(1 if same(a, b) else 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin
n, q = map(int, stdin.readline().split())
ans = []
ans_append = ans.append
high = [0] * n
par = [i for i in range(n)]
def findSet(x):
    if par[x] == x: return x
    par[x] = findSet(par[x])
    return par[x]
def unite(x, y):
    x = findSet(x)
    y = findSet(y)
    if x == y: return
    if high[x] > high[y]: par[y] = x;
    else:
        par[x] = y
        if high[x] == high[y]: high[y] += 1
def same(x, y):
    return findSet(x) == findSet(y)
for i in range(q):
    t, a, b = map(int, stdin.readline().split())
    if t == 0: unite(a, b);
    elif t == 1: ans_append(1 if same(a, b) else 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class DisjointSet(object):
    rank = []
    p = []

    def __init__(self, size):
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        DisjointSet.p.insert(x, x)
        DisjointSet.rank.insert(x, 0)


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


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


    def link(self, x, y):
        if DisjointSet.rank[x] > DisjointSet.rank[y]:
            DisjointSet.p[y] = x
        else:
            DisjointSet.p[x] = y
            if DisjointSet.rank[x] == DisjointSet.rank[y]:
                DisjointSet.rank[y] += 1


    def findSet(self, x):
        if x != DisjointSet.p[x]:
            DisjointSet.p[x] = self.findSet(DisjointSet.p[x])
        return DisjointSet.p[x]



if __name__ == '__main__':
    # ??????????????\???
    n, q  = input().split(' ')
    data = []
    for i in range(int(q)):
        data.append(list(map(int, input().split(' '))))

    ds = DisjointSet(int(n))
    for d in data:
        command, x, y = d
        if command == 0:
            ds.unite(x, y)
        elif command == 1:
            result = ds.same(x, y)
            if result:
                print('1')
            else:
                print('0')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

N, Q = tuple(map(int, input().split()))

tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group

def unite(x, y):
    px = find(x)
    py = find(y)
    
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

for _ in range(Q):
    com, x, y = tuple(map(int, input().split()))
    if com: # same
        print(int(find(x) == find(y)))
    else: # unite
        if not int(find(x) == find(y)):
            unite(x, y)

Submission status: Accepted

Solution code:
import sys
N, Q = map(int, input().split())

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def union(x,y):
    rx, ry = find(x), find(y)
    par[ry] = rx
    
for _ in range(Q):
    p,a,b = map(int, sys.stdin.readline().split())
    if p == 0:
        union(a, b)
    if p == 1:
        if find(a) != find(b):
            print(0)
        else:
            print(1)

Submission status: Accepted

Solution code:
# encoding: "utf-8"

class Unreachable(Exception):
    pass


class SetManager:
    def __init__(self, n):
        self.data = list()
        for i in range(n):
            self.data.append((i, {i}))

    def ref(self, i):
        return self.data[i][1]

    def set(self, i, value):
        self.data[i] = (i, value)

    def find_set(self, i):
        value = self.ref(i)
        if isinstance(value, set):
            return self.data[i]
        elif isinstance(value, int):
            result = self.find_set(value)
            self.set(i, result[0])
            return result
        else:
            raise Unreachable

    def run(self, command):
        com, x, y = command
        if com == 0:
            # unite
            i, setx = self.find_set(x)
            j, sety = self.find_set(y)
            if i != j:
                new_set = setx | sety
                self.set(i, new_set)
                self.set(j, i)

        elif com == 1:
            # same
            if y in self.find_set(x)[1]:
                print(1)
            else:
                print(0)
        else:
            raise Unreachable

def main():
    n, q = [int(x) for x in input().split()]
    manager = SetManager(n)

    commands = list()
    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        commands.append((com, x, y))
    
    for command in commands:
        manager.run(command)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# encoding: "utf-8"

from enum import Enum

class Unreachable(Exception):
    pass

class Type(Enum):
    VAL = 0
    PTR = 1


class Elem:
    def __init__(self, i, value, _type):
        self.idx = i
        self.value = value
        self.type = _type

    def set(self, value, _type):
        self.value = value
        self.type = _type
        

class SetManager:
    def __init__(self, n):
        self.data = list()
        for i in range(n):
            self.data.append(Elem(i, {i}, Type.VAL))

    def get(self, i):
        return self.data[i]

    def set(self, i, value):
        if isinstance(value, set):
            t = Type.VAL
        elif isinstance(value, int):
            t = Type.PTR
        self.data[i].set(value, t)

    def find_root(self, i):
        elem = self.get(i)
        if elem.type == Type.VAL:
            return (i, elem)
        elif elem.type == Type.PTR:
            j, root_elem = self.find_root(elem.value)
            self.set(i, j)
            return (j, root_elem)
        else:
            raise Unreachable

    def run(self, command):
        com, x, y = command
        if com == 0:
            self.unite(x, y)

        elif com == 1:
            if self.same(x, y):
                print(1)
            else:
                print(0)

        else:
            raise Unreachable

    def unite(self, x, y):
        i, elem_x = self.find_root(x)
        j, elem_y = self.find_root(y)
        if i != j:
            new_set = elem_x.value | elem_y.value
            self.set(i, new_set)
            self.set(j, i)

    def same(self, x, y):
        return y in self.find_root(x)[1].value


def main():
    n, q = [int(x) for x in input().split()]
    manager = SetManager(n)

    commands = list()
    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        commands.append((com, x, y))
    
    for command in commands:
        manager.run(command)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# encoding: "utf-8"

from enum import Enum

class Unreachable(Exception):
    pass


class Type(Enum):
    VAL = 0
    PTR = 1


class Elem:
    def __init__(self, i, value, _type):
        self.idx = i
        self.value = value
        self.type = _type

    def set(self, value, _type):
        self.value = value
        self.type = _type
        

class SetManager:
    def __init__(self, n):
        self.data = list()
        for i in range(n):
            self.data.append(Elem(i, {i}, Type.VAL))

    def get(self, i):
        return self.data[i]

    def set(self, i, value):
        if isinstance(value, set):
            t = Type.VAL
        elif isinstance(value, int):
            t = Type.PTR
        self.data[i].set(value, t)

    def find_root(self, i):
        elem = self.get(i)
        if elem.type == Type.VAL:
            return (i, elem)
        elif elem.type == Type.PTR:
            j, root_elem = self.find_root(elem.value)
            self.set(i, j)
            return (j, root_elem)
        else:
            raise Unreachable

    def run(self, command):
        com, x, y = command
        if com == 0:
            self.unite(x, y)

        elif com == 1:
            if self.same(x, y):
                print(1)
            else:
                print(0)

        else:
            raise Unreachable

    def unite(self, x, y):
        i, elem_x = self.find_root(x)
        j, elem_y = self.find_root(y)
        if i != j:
            new_set = elem_x.value | elem_y.value
            self.set(i, new_set)
            self.set(j, i)

    def same(self, x, y):
        return y in self.find_root(x)[1].value


class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, n, converter):
        assert(n == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def main():
    n, q = Stdin.read_line(int)
    manager = SetManager(n)
    commands = Stdin.read_lines(q, int)
    
    for command in commands:
        manager.run(command)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
rank = {}
p = {}
        
def makeSet(x):
    p[x] = x
    rank[x] = 0

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

def union(x, y):
    link(findSet(x), findSet(y))
    
def findSet(x):
    if  x != p[x]:
        p[x] = findSet(p[x])
    return p[x]
    
def isSameSet(x, y):
    return findSet(x) == findSet(y)

n, q = map(int, input().split())
for x in range(n):
    makeSet(x)

for i in range(q):
    a,x,y = map(int, input().split())
    ret = (union if a == 0 else isSameSet)(x,y)
    if ret is None: continue
    if ret == True: print(1)
    else: print(0)

Submission status: Accepted

Solution code:
def main():
    n,q = map(int,raw_input().split())

    ds = DisjointSet(n)

    for i in xrange(q):
        com,x,y = map(int,raw_input().split())
        if com:
            ds.findSet(x)
            ds.findSet(y)
            if ds.parent[x] == ds.parent[y]:
                print 1
            else:
                print 0
        else:
            ds.findSet(x)
            ds.findSet(y)
            ds.unite(x,y)

class DisjointSet():
    def __init__(self,n):
        self.n = n
        self.parent = range(n)

    def findSet(self,x):
        if self.parent[x] == x:
            return x
        else:
            p = self.findSet(self.parent[x])
            self.parent[x] = p
            return p

    def unite(self,x,y):
        if self.parent[y] > self.parent[x]:
            self.parent[self.parent[y]] = self.parent[x]
        else:
            self.parent[self.parent[x]] = self.parent[y]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    import sys
    sys.setrecursionlimit(100000)

    def __init__(self, v_num):
        self.parent = [n for n in range(v_num)]
        self.rank = [0 for n in range(v_num)]

    def find(self, v):
        if v == self.parent[v]:
            return v
        else:
            root = self.find(self.parent[v])
            self.parent[v] = root
            return root

    def unite(self, a_v, other_v):
        a_root = self.find(a_v)
        other_root = self.find(other_v)
        if a_root == other_root:
            return
        if self.rank[a_root] < self.rank[other_root]:
            self.parent[a_root] = other_root
        else:
            self.parent[other_root] = a_root
            if self.rank[a_root] == self.rank[other_root]:
                self.rank[a_root] += 1

    def same(self, a_v, other_v):
        return self.find(a_v) == self.find(other_v)

v_num, query = (int(n) for n in input().split(" "))
uf = UnionFind(v_num)
for _ in range(query):
    com, a, b = (int(n) for n in input().split(" "))
    if com == 0:
        uf.unite(a, b)
    else:
        if uf.same(a, b):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
# It took me about 40 minutes to finsih this assignment.
# The task itself is relatively simple, since we have sample code on handouts.
# One problem I met was that in case 22, I had a "RecursionError" (maximum recursion depth exceeded in comparison).
# The solution was simple: import sys, and add a line "sys.setrecursionlimit(100000)".

import sys

line = input().split()
n = int(line[0])
q = int(line[1])
mat = [0]*n
for i in range(n):
	mat[i]=i
sys.setrecursionlimit(100000)

def root(a):
	if mat[a]==a:
		return a
	else:
		mat[a] = root(mat[a])
		return mat[a]

def union(a, b):
	mat[root(a)]=root(b)

def is_same(a,b):
	if root(a) == root(b):
		return 1
	else:
		return 0

for i in range(q):
	line = input().split()
	a = int(line[0])
	line[1]=int(line[1])-1
	line[2]=int(line[2])-1
	if a==0:
		union(mat[line[1]],mat[line[2]])
	if a==1:
		print(is_same(mat[line[1]],mat[line[2]]))