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: Runtime Error

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

def unite(list_s, x, y):
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            x_list = list_s[idx]
        if y in list_s[idx]:
            for num in list_s[idx]:
                x_list.append(num)
            del list_s[idx]
    return list_s


def same(list_s, x, y):
    result_flg = 0
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            if y in list_s[idx]:
                result_flg = 1
                break
    return result_flg



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

S = [[y] for y in [x for x in range(n)]]

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

Submission status: Runtime Error

Solution code:
# Disjoint Set: Union Find Trees
[p, rank] = [[], []]
[n, q] = list(map(int, input().split()))
w = [0 for i in range(n)]
path_c = [[] for i in range(n)]

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]

def link(x, y):
    global p, rank
    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 same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

def relate(x, y, z):
    global w, path_c
    path_c[x].append((y, z))
    #print(w)
    if w[y] == 0:
        w[y] = w[x] + z
    else:
        update(x, y, z)
        #w[x] = w[y] - z
    #print("cost:", w[y])
    union(x, y)

def update(x, y, z):
    global w, path_c
    w[x] = w[y] - z
    for i in range(len(path_c[x])):
        update(path_c[x][i][0], x, path_c[x][i][1])


def diff(x, y):
    if same(x, y) == 1:
        global w
        return abs(w[y] - w[x])
        '''
        global d
        total = 0
        d = [0 for i in range(n)]
        d[x] = 1
        return cost(x, y, n, total)
        '''
    else:
        return "?"     

'''
print(p)
print(rank)
print(w)
print("\n")
'''

for i in range(n):
    makeSet(i)

#w = [0 for i in range(n)]

for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        relate(data[1], data[2], data[3])
    else:
        print(diff(data[1], data[2]))
    '''
    print("\n")
    print(p)
    print(rank)
    print(w)
    print("\n")
    '''

Submission status: Runtime Error

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

ss = [set([i]) for i in range(n)]

for _ in range(nq):
    q,x,y = map(int, input().split())
    if q == 0:
        sx = {}
        sy = {}
        for s in ss:
            if x in s:
                sx = s
            if y in s:
                sy = s
        ss.remove(sx)
        ss.remove(sy)
        ss.append(sx | sy)
    else:
        for s in ss:
            if x in s:
                if y in s:
                    print(1)
                else:
                    print(0)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, max_size):
        self.max_size = max_size
        self.dat = [i for i in range(self.max_size)]

    def find(self, vertex):
        if self.dat[vertex] is vertex: return vertex
        self.dat[vertex] = self.find(self.dat[vertex])
        return self.dat[vertex]

    def merge(self, child, parent):
        """
        parentとchildをマージして、parentの所属にする
        :param parent:
        :param child:
        :return:
        """
        self.dat[self.find(child)] = self.dat[self.find(parent)]

    def is_same(self, v, w):
        """
        頂点vと頂点wが同じ集合に所属しているか
        :param v:
        :param w:
        :return:
        """
        return self.find(v) == self.find(w)


n, q = map(int, input().split())
uni = UnionFind(n)
while q > 0:
    q -= 1
    com, x, y = map(int, input().split())
    if com is 0:
        uni.merge(x, y)
    else:
        print(1 if uni.is_same(x, y) else 0)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int root(int i,vector<int> &set){
    if(set[i]==-1){
        return i;
    }else{
        int result=root(set[i],set);
        set[i]=result;
        return result;
    }
}
int main(){
    int n,q;
    cin >> n >> q;
    vector<int> set(n,-1);
    for(int i=0;i<q;++i){
        int com,x,y;
        cin >> com >> x >> y;
        if(com==0){
            //unite
            set[root(y,set)]=root(x,set);
        }else{
            //same
            if(root(x,set)==root(y,set)){
                cout << 1 << endl;
            }else{
                cout << 0 << endl;
            }
        }
    }
}

Submission status: Runtime Error

Solution code:

class UnionFindTree:

    def __init__(self):
        self.cnt = []
        self.par = []

    def add(self, n):
        assert n == len(self.par), "Invalid Value"
        self.par.append(n)
        self.cnt.append(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(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:
            self.cnt[x] = self.cnt[x] + self.cnt[y]
            self.cnt[y] = self.cnt[x]
            self.par[x] = y

    def size(self, x):
        x = self.find(x)
        return self.cnt[x]


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def get():
	return input()
	
def lastIndex(ref, i):
	if ref[i] == i:
		return i
	else:
		return lastIndex(ref, ref[i])

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

ref = list(range(n))
for _ in range(q):
	com, a, b = map(int, get().split())
	if com == 0:
		# unit
		ref[lastIndex(ref, b)] = lastIndex(ref, a)
	else:
		# same
		if lastIndex(ref, b) == lastIndex(ref, a):
			print("1")
		else:
			print("0")

Submission status: Runtime Error

Solution code:
def get():
    return input()
     
def lastIndex(ref, i):
    if ref[i] == i:
        return i
    else:
        return lastIndex(ref, ref[i])
 
n, q = map(int, get().split())
 
ref = list(range(n))
for _ in range(q):
    com, a, b = map(int, get().split())
    if com == 0:
        # unit
        ref[lastIndex(ref, b)] = lastIndex(ref, a)
    else:
        # same
        if lastIndex(ref, b) == lastIndex(ref, a):
            print("1")
        else:
            print("0")

Submission status: Runtime Error

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n, q = (int(s) for s in stdin.readline().split())
    s = [{i} for i in range(n)]

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            for si in s:
                if x in si and y in si:
                    print(1)
                    break
            else:
                print(0)
        else:
            for si in s:
                if x in si:
                    a = si
                elif y in si:
                    b = si
            s.append(a | b)
            s.remove(a)
            s.remove(b)


main()

Submission status: Runtime Error

Solution code:
n,q = map(int, raw_input().split())
S = [set([i]) for i in range(n)]
ref = [0]*n
for i in range(q):
	com,x,y = map(int, raw_input().split())
	if x > y: x,y = y,x
	if com == 0: # unite
		x += ref[x]; y += ref[y]
		S[x] = S[x]|S[y]
		S.pop(y)
		for j in range(y,n):
			ref[j] -= 1
	else: # same
		print 1 if y in S[x+ref[x]] else 0