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: Time Limit Exceeded

Solution code:
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 == 0:
        indexx,indexy = -1,-1
        for j in range(len(s)):
            if x in s[j]:
                indexx = j
            if y in s[j]:
                indexy = j
            if indexx >= 0 and indexy >= 0:
                break
        if indexx != indexy:
            s[indexx].extend(s[indexy])
            s.remove(s[indexy])
    if com == 1:
        for j in range(len(s)):
            if x in s[j]:
                if y in s[j]:
                    print(1)
                else:
                    print(0)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

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

def unite(sets, v1, v2):
    s1 = None
    s2 = None
    for s in sets:
        if v1 in s and v2 in s:
            return None
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
        if s1 and s2:
            break
    sets.append(s1 + s2)
    sets.remove(s1)
    sets.remove(s2)

def same(sets, v1, v2):
    for s in sets:
        if v1 in s and v2 in s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

Submission status: Time Limit Exceeded

Solution code:
import sys

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

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

def unite(sets, v1, v2):
    s1 = None
    s2 = None
    t_s = frozenset([v1, v2])
    for s in sets:
        if t_s <= s:
            return None
        elif s1 and s2:
            break
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
    sets.discard(s1)
    sets.discard(s2)
    s3 = s1.union(s2)
    sets.add(s3)

def same(sets, v1, v2):
    t_s = frozenset([v1, v2])
    for s in sets:
        if t_s <= s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())
 
S = set([frozenset([i]) for i in range(n)])
 
def unite(sets, v1, v2):
    s1 = None
    s2 = None
    t_s = {v1, v2}
    for s in sets:
        if t_s <= s:
            return None
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
        if s1 and s2:
            break
    sets.discard(s1)
    sets.discard(s2)
    s3 = s1.union(s2)
    sets.add(s3)
 
def same(sets, v1, v2):
    for s in sets:
        t_s = {v1, v2}
        if t_s <= s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break
 
for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

Submission status: Time Limit Exceeded

Solution code:
def find_group(x):
    return [x in g for g in groups].index(True)

n, q = map(int, raw_input().split())
groups = [set([i]) for i in range(n)]

for i in range(q):
    com, x, y = map(int, raw_input().split())
    if com == 0:
        ind1 = find_group(x)
        ind2 = find_group(y)
        if ind1 != ind2:
            g1 = groups[ind1]
            g2 = groups[ind2]
            groups.append(g1.union(g2))
            
            groups.remove(g1)
            groups.remove(g2)
 
    elif com == 1:
        ind1 = find_group(x)
        ind2 = find_group(y)
        
        print int(ind1 == ind2)
        
    #print com, x, y, groups

Submission status: Time Limit Exceeded

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
        while self.parent[r]!=r:
            r = self.parent[r]
        return r

    def unite(self,x,y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        if rx!=ry: 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: Time Limit Exceeded

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
        while self.parent[r]!=r:
            r = self.parent[r]
            depth += 1
        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: Time Limit Exceeded

Solution code:
def unite(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            x_list = s.copy()
            y_list = s.copy()
            del s
        elif x in s:
            x_list = s.copy()
            del s
        elif y in s:
            y_list = s.copy()
            del s
    if x_list != None and y_list != None:
        s_list.append(list(set(x_list + y_list)))
    elif x_list != None and y_list == None:
        x_list.append(y)
        s_list.append(x_list)
    elif x_list == None and y_list != None:
        y_list.append(x)
        s_list.append(y_list)
    else:
        s_list.append([x, y])

def same(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            return 1
    return 0


n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()
s_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)

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]
    if com == 0:
        unite(x, y, s_list)
    else:
        result = same(x, y, s_list)
        print(result)

Submission status: Time Limit Exceeded

Solution code:
class myQuery:
    def __init__(self,n):
        self.lists = [[i] for i in range(n)]

    def unite(self, x, y):
        for i in range(len(self.lists)):
            if x in self.lists[i]:
                for j in range(i+1, len(self.lists)):
                    if y in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return
            elif y in self.lists[i]:
                for j in range(i+1, len(self.lists)):
                    if x in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return

    def same(self, x, y):
        for li in self.lists:
            if x in li and y in li:
                return print(1)
            elif x in li or y in li:
                break
        return print(0)



def main():
    n, q = map(int, input().split())
    qu = myQuery(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            qu.unite(x,y)
        if com == 1:
            qu.same(x,y)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class myQuery:
    def __init__(self,n):
        self.lists = [[i] for i in range(n)]

    def unite(self, x, y):
        for i in range(len(self.lists)):
            if x in self.lists[i]:
                if y in self.lists[i]:
                    return
                for j in range(i+1, len(self.lists)):
                    if y in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return
            elif y in self.lists[i]:
                if x in self.lists[i]:
                    return
                for j in range(i+1, len(self.lists)):
                    if x in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return

    def same(self, x, y):
        for li in self.lists:
            if x in li and y in li:
                return print(1)
            elif x in li or y in li:
                break
        return print(0)



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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
PARENT = {}
import sys
sys.setrecursionlimit(10**8)


def MAKE_SET(v):
    PARENT.update({v : v})

def FIND_SET(u):
    if PARENT[u] == u:
        return u
    else:
        return FIND_SET(PARENT[u])

def UNION(u, v):
    u_root = FIND_SET(u) 
    v_root = FIND_SET(v)
    PARENT[u_root] = v_root

def SAME(u, v):
    return FIND_SET(u) == FIND_SET(v)

n, q = raw_input().split(' ')
for i in range(int(n)):
    MAKE_SET(i)

for _ in range(int(q)):
    query_type, x, y = raw_input().split(' ')

    if query_type == '0':
        # unite
        UNION(int(x), int(y))

    else:
        # same:
        if SAME(int(x), int(y)):
            print 1
        else:
            print 0

Submission status: Time Limit Exceeded

Solution code:
# encoding: "utf-8"

class Unreachable(Exception):
    pass

def main():
    n, q = [int(x) for x in input().split()]
    setlist = list()
    for i in range(n):
        setlist.append({i})

    for _ in range(q):
        run(setlist)


def run(setlist):
    com, x, y = [int(x) for x in input().split()]
    if com == 0:
        # unite
        new_set = setlist[x] | setlist[y]
        for i in new_set:
            setlist[i] = new_set

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# encoding: "utf-8"

class Unreachable(Exception):
    pass

def main():
    n, q = [int(x) for x in input().split()]
    setlist = list()
    for i in range(n):
        setlist.append({i})

    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:
        run(setlist, command)


def run(setlist, command):
    com, x, y = command
    if com == 0:
        # unite
        new_set = setlist[x] | setlist[y]
        for i in new_set:
            setlist[i] = new_set

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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:
            if ds.root[x] == ds.root[y]:
                print 1
            else:
                print 0
        else:
            ds.unite(x,y)

class DisjointSet():
    def __init__(self,n):
        self.n = n
        self.root = range(n)
        self.parent = [-1]*n
        self.rank = [0]*n

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

    def unite(self,x,y):
        if self.rank[x] > self.rank[y]:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[y]]:
                self.parent[z] = self.root[x]
                self.root[z] = self.root[x]
                self.rank[z] = self.rank[x]
        elif self.rank[x] < self.rank[y]:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[x]]:
                self.parent[z] = self.root[y]
                self.root[z] = self.root[y]
                self.rank[z] = self.rank[y]
        else:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[x]]:
                self.parent[z] = self.root[y]
                self.root[z] = self.root[y]
                self.rank[z] = self.rank[y]+1

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def is_in_sameset(S, x, y) :
    if x <= S and y <= S :
        return True
    else :
        return False


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

    com = []
    x = []
    y = []

    for _ in range(q) :
        tmp = input().split()
        com.append(int(tmp[0]))
        x.append(int(tmp[1]))
        y.append(int(tmp[2]))



    for i in range(q) :
        if com[i] == 0 :
            set1 = set()
            set2 = set()
            for set_item in set_list :
                if set([x[i]]) <= set_item :
                    set1 = set_item
                    #set_list.remove(set_item)
                if set([y[i]]) <= set_item :
                    set2 = set_item
                    #set_list.remove(set_item)

            union_set = set1 | set2
            if set1 in set_list :
                set_list.remove(set1)
            if set2 in set_list :
                set_list.remove(set2)
            set_list.append(union_set)
        elif com[i] == 1 :
            flag = False
            for set_item in set_list :
                if is_in_sameset(set_item, set([x[i]]), set([y[i]])) :
                    flag = True
            if flag :
                print("1")
            else :
                print("0")


if __name__ == '__main__' :
    main()

Submission status: Time Limit Exceeded

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

s =[set([i]) for i in range(n)]
p =[i for i in range(n)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if y in s[p[x]]: print(1)
        else: print(0)
    else:
        s[p[x]] = s[p[x]] | s[p[y]]
        p_x_tmp = p[x]
        p_y_tmp = p[y]
        for j in range(n):
            if p[j] == p_y_tmp: p[j] = p_x_tmp

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
	N, p = input().split()
	N, p = int(N), int(p)

	numdict = {str(i):i for i in range(N)}

	for i in range(p):
		que, x, y = input().split()
		if int(que):
			if numdict[x] == numdict[y]:
				print(1)
			else:
				print(0)

		else:
			if numdict[x] <= numdict[y]:
				m = numdict[y]
				n = numdict[x]
			
			else:
				m = numdict[x]
				n = numdict[y]
			
			for i in numdict:
				if numdict[i] == m:
					numdict[i] = n
				else:
					continue

Submission status: Time Limit Exceeded

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

def unite(list_s, x, y):
    x_idx, y_idx = 0, 0
    x_list, y_list= None, None
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            x_idx = idx
            x_list = list_s[idx]
        if y in list_s[idx]:
#            for num in list_s[idx]:
            y_idx = idx
            y_list = list_s[idx]
    if (x_list is not None) and (y_list is not None):
        for num in y_list:
            if x_list != y_list:
                list_s[x_idx].append(num)
                list_s[x_idx] = sorted(list_s[x_idx])
        if x_idx != y_idx:
            del list_s[y_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: Time Limit Exceeded

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

def unite(list_s, x, y):
    x_idx, y_idx = 0, 0
    x_list, y_list= None, None
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            x_idx = idx
            x_list = list_s[idx]
        if y in list_s[idx]:
            y_idx = idx
            y_list = list_s[idx]
    if (x_list is not None) and (y_list is not None):
        if x_list != y_list:
            list_s[x_idx].extend(y_list)
            list_s[x_idx] = sorted(list_s[x_idx])
        if x_idx != y_idx:
            del list_s[y_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: Time Limit Exceeded

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

def unite(list_s, x, y):
    x_idx, y_idx = 0, 0
    x_list, y_list= None, None
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            x_idx = idx
            x_list = list_s[idx]
            continue
        if y in list_s[idx]:
            y_idx = idx
            y_list = list_s[idx]
            continue
    if (x_list is not None) and (y_list is not None):
        if x_list != y_list:
            list_s[x_idx].extend(y_list)
            list_s[x_idx] = sorted(list_s[x_idx])
        if x_idx != y_idx:
            del list_s[y_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: Time Limit Exceeded

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

def unite(list_s, x, y):
    x_idx, y_idx = 0, 0
    x_list, y_list= None, None
    for idx, elem in enumerate(list_s):
        if x in list_s[idx]:
            x_idx = idx
            x_list = list_s[idx]
            continue
        if y in list_s[idx]:
            y_idx = idx
            y_list = list_s[idx]
            continue
    if (x_list is not None) and (y_list is not None):
        if x_list != y_list:
            list_s[x_idx].extend(y_list)
        if x_idx != y_idx:
            del list_s[y_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: Time Limit Exceeded

Solution code:
#! python3
# disjoint_set_union_find_tree.py

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

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

def unite(Sx, Sy):
    return Sx | Sy

def search(x):
    global sets
    flag = False
    for i in range(len(sets)):
        if x in list(sets[i]):
            flag = True
            break
    if flag:
        return i
    else:
        return None

def same(x, y):
    global sets
    flag = 0
    for set in sets:
        if x in set:
            if y in set:
                 flag = 1
            break
    return flag

for i in range(q):
    query, x, y = input().split(' ')
    x, y = int(x), int(y)
    if query == '0':
        # unite
        i_x = search(x)
        i_y = search(y)
        if i_x != None and i_y != None and i_x != i_y:
            sets[i_x] = unite(sets[i_x], sets[i_y])
            del sets[i_y]
    elif query == '1':
        # same
        print(same(x, y))

Submission status: Time Limit Exceeded

Solution code:
def get():
	return input()

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
		x = ref[a]
		for i in range(n):
			if ref[i] == x:
				ref[i] = ref[b]
	else:
		# same
		if ref[a] == ref[b]:
			print("1")
		else:
			print("0")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,raw_input().split())

arr = []

for i in range(n):
	arr.append(i)

def root(i):
	t = i
	while arr[t] != t:
		t = arr[t]

	return t

for i in range(m):
	query,x,y = map(int,raw_input().split())

	if query == 0:
		arr[root(y)] = x

	else :
		print 1 if root(x) == root(y) else 0

Submission status: Time Limit Exceeded

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
                if y in si:
                    b = si
            if a != b:
                s.append(a | b)
                s.remove(a)
                s.remove(b)


main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, raw_input().split())
ls = [set([i]) for i in range(n)]
for i in range(q):
	com,x,y = map(int, raw_input().split())
	if com == 0: # unite
		ls[x] = ls[x]|ls[y]
		for i in list(ls[x]):
			ls[i] = ls[x]
	else: # same
		print 1 if y in ls[x] and x in ls[y] else 0

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, raw_input().split())
ls = [set([i]) for i in range(n)]
ref = [i for i in range(n)]
for i in range(q):
	com,x,y = map(int, raw_input().split())
	if com == 0: # unite
		x = ref[x]
		ls[x] = ls[x]|ls[ref[y]]
		for i in list(ls[x]):
			ref[i] = ref[x]
	else: # same
		print 1 if y in ls[ref[x]] and x in ls[ref[y]] else 0

Submission status: Memory Limit Exceeded

Solution code:
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp
#  Disjoint Set: Union Find Tree : python3
#  2018.12.23 yonezawa

#from collections import deque
import sys
input = sys.stdin.readline
#import cProfile
#from math import cos,sin,radians,sqrt
from collections import deque

def main():
    (n,q) = map(int,input().split())
    s = [[i] for i in range(n)]
    for i in range(q):
        (a,b,c) = map(int,input().split())
        if a == 0:
            n1 = s[b]
            n2 = s[c]
            n1.extend(n2)
            for j in n1:
                s[j] = n1
        elif a == 1:
            if c in s[b] or n in s[c]:
                print ("1")
            else:
                print("0")
    
if __name__ == '__main__':
    main()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

Submission status: Memory Limit Exceeded

Solution code:
def union(x, y):
    X = None
    Y = None
    xi = None
    yi = None
    for i, n in enumerate(S):
        if x in n:
            xi = i
            X = n
        if y in n:
            yi = i
            Y = n
    for y in Y:
        X.append(y)
    S[yi] = []

def same(x, y):
    xi = -1
    yi = -100
    for i, n in enumerate(S):
        if x in n:
            xi = i
        if y in n:
            yi = i
        if 0 <= yi and 0 <= xi:
            return xi == yi
    return False


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

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

Submission status: Memory Limit Exceeded

Solution code:
class myQuery:
    def __init__(self,n):
        self.lists = [[i] for i in range(n)]

    def unite(self, x, y):
        for i in range(len(self.lists)):
            if x in self.lists[i]:
                for j in range(i, len(self.lists)):
                    if y in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return
            elif y in self.lists[i]:
                for j in range(i, len(self.lists)):
                    if x in self.lists[j]:
                        for ele in self.lists[j]:
                            self.lists[i].append(ele)
                        self.lists.pop(j)
                        return

    def same(self, x, y):
        for li in self.lists:
            if x in li and y in li:
                return print(1)
            elif x in li or y in li:
                break
        return print(0)



def main():
    n, q = map(int, input().split())
    qu = myQuery(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            qu.unite(x,y)
        if com == 1:
            qu.same(x,y)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class UF:
    """Union Find
    """
    def __init__(self, n):
        self.n = n
        self.elements = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def union(self, v, w):
        assert 0 <= v < self.n
        assert 0 <= w < self.n
        rv = self.root(v)
        rw = self.root(w)

        if rv != rw:
            if self.size[rv] > self.size[rw]:
                self.elements[rw] = rv
                self.size[rv] += self.size[rw]
            else:
                self.elements[rv] = rw
                self.size[rw] += self.size[rv]

    def connected(self, v, w):
        assert 0 <= v < self.n
        assert 0 <= w < self.n
        return self.root(v) == self.root(w)

    def root(self, v):
        rv = self.elements[v]
        while rv != self.elements[rv]:
            rv = self.elements[rv]
        return rv


def run():
    n, q = [int(x) for x in input().split()]
    uf = UF(n)

    for _ in range(q):
        com, i, j = [int(x) for x in input().split()]
        if com == 0:
            uf.union(i, j)
        elif com == 1:
            if uf.connected(i, j):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
union = [x for x in range(N)]
answer_list = []

def fetch_root(idx) :
    if idx == union[idx] :
        return idx
    else :
        union[idx] = fetch_root(union[union[idx]])
        return union[idx]

for i in range(Q) :
    q, a, b = map(int, input().split())
    
    # uinon
    if q == 0 :
        min_root_idx = max(fetch_root(a), fetch_root(b))
        union[min_root_idx] = min(fetch_root(a), fetch_root(b))
        
    # evaluate
    else :
        if fetch_root(union[a]) == fetch_root(union[b]) :
            answer_list.append(1)
        else :
            answer_list.append(0)
            
for i in answer_list :
    print(i)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
union = [x for x in range(n)]
answer = []

def root(idx) :
    if idx == union[idx] :
        return idx
    else :
        union[idx] = root(union[idx])
        return union[idx]

for i in range(q) :
    com, x, y = map(int, input().split())
    
    # union
    if com == 0 :
        min_root = min(root(x), root(y))
        union[root(x)] = union[root(y)] = min_root
        
    # non-union
    else :
        if root(x) == root(y) :
            answer.append("1")
        else :
            answer.append("0")
            
for i in answer :
    print(i)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
nodes = [x for x in range(n)]
answer = []

def get_root(idx) :
    if idx == nodes[idx] :
        return idx
    else :
        nodes[idx] = get_root(nodes[idx])
        return nodes[idx]
        
for i in range(p) :
    q, a, b = map(int, input().split())
    
    # union 
    if q == 0 :
        parent_min = min(get_root(a), get_root(b))
        nodes[get_root(a)] = nodes[get_root(b)] = parent_min
        
    # check
    else :
        if get_root(a) == get_root(b) : answer.append(1)
        else : answer.append(0)
            
for i in answer :
    print(i)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
nodes = [x for x in range(n)]
answer = []

def get_root(idx) :
    if idx == nodes[idx] :
        return idx
    else :
        # nodes[idx] = get_root(nodes[idx])
        return get_root(nodes[idx])
        
for i in range(p) :
    q, a, b = map(int, input().split())
    
    # union 
    if q == 0 :
        parent_min = min(get_root(a), get_root(b))
        nodes[get_root(a)] = nodes[get_root(b)] = parent_min
        
    # check
    else :
        if get_root(a) == get_root(b) : answer.append(1)
        else : answer.append(0)
            
for i in answer :
    print(i)