Submission #1689070


Source Code Expand

class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    
    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x
    
    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return

N,Q = map(int,input().split())
G = UnionFind(N)
res = []
for i in range(Q):
    P,A,B = map(int,input().split())
    if P == 1:
        if G.find(A) == G.find(B):
            res.append('Yes')
        else:
            res.append('No')
    else:
        if A != B:#自己ループは実装しない
            G.union(A,B)


for s in res:
    print(s)

Submission Info

Submission Time
Task B - Union Find
User hukuhuku11111
Language Python (3.4.3)
Score 100
Code Size 1527 Byte
Status AC
Exec Time 836 ms
Memory 6528 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 21 ms 3444 KB
subtask_01_01.txt AC 512 ms 4956 KB
subtask_01_02.txt AC 22 ms 3992 KB
subtask_01_03.txt AC 770 ms 5736 KB
subtask_01_04.txt AC 814 ms 6512 KB
subtask_01_05.txt AC 70 ms 3572 KB
subtask_01_06.txt AC 75 ms 4628 KB
subtask_01_07.txt AC 790 ms 5764 KB
subtask_01_08.txt AC 823 ms 6528 KB
subtask_01_09.txt AC 17 ms 3064 KB
subtask_01_10.txt AC 22 ms 3992 KB
subtask_01_11.txt AC 801 ms 5660 KB
subtask_01_12.txt AC 782 ms 6512 KB
subtask_01_13.txt AC 622 ms 5280 KB
subtask_01_14.txt AC 23 ms 3888 KB
subtask_01_15.txt AC 784 ms 5760 KB
subtask_01_16.txt AC 833 ms 6516 KB
subtask_01_17.txt AC 820 ms 5520 KB
subtask_01_18.txt AC 836 ms 5492 KB