Submission #7025901


Source Code Expand

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

n,q=map(int,input().split())
gragh=Union_find(n+1)
for _ in range(q):
    p,a,b=map(int,input().split())
    if p:
        print("Yes"if gragh.same(a,b) else "No")
    else:
        gragh.unite(a,b)

Submission Info

Submission Time
Task B - Union Find
User naru1
Language Python (3.4.3)
Score 100
Code Size 1113 Byte
Status AC
Exec Time 1790 ms
Memory 5236 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 17 ms 3064 KB
subtask_01_01.txt AC 1042 ms 3572 KB
subtask_01_02.txt AC 20 ms 4596 KB
subtask_01_03.txt AC 1729 ms 3828 KB
subtask_01_04.txt AC 1735 ms 5236 KB
subtask_01_05.txt AC 121 ms 3064 KB
subtask_01_06.txt AC 119 ms 4724 KB
subtask_01_07.txt AC 1706 ms 3828 KB
subtask_01_08.txt AC 1696 ms 5236 KB
subtask_01_09.txt AC 18 ms 3064 KB
subtask_01_10.txt AC 21 ms 4596 KB
subtask_01_11.txt AC 1710 ms 3700 KB
subtask_01_12.txt AC 1734 ms 5236 KB
subtask_01_13.txt AC 1405 ms 3572 KB
subtask_01_14.txt AC 24 ms 4596 KB
subtask_01_15.txt AC 1688 ms 3700 KB
subtask_01_16.txt AC 1790 ms 5236 KB
subtask_01_17.txt AC 1438 ms 4980 KB
subtask_01_18.txt AC 1498 ms 4980 KB