Submission #39447892

Source Code Expand

class Union:
    def __init__(self, n):
        self.ls = [i for i in range(n)]
        self.vsize = [1] * n
        self.esize = [0] * n
        
    def find(self, i):
        if self.ls[i] != i:
            self.ls[i] = self.find(self.ls[i])
        return self.ls[i]
    
    def link(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i != j:
            if self.vsize[i] > self.vsize[j]:
                i, j = j, i
            self.ls[i] = j
            self.vsize[j] += self.vsize[i]
            self.esize[j] += self.esize[i] + 1
        else:
            self.esize[j] += 1

n, m = [int(i) for i in input().split()]
U = Union(n)
for _ in range(m):
    u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    U.link(u, v)
for i in range(n):
    j = U.find(i)
    if U.vsize[j] != U.esize[j]:
        print('No')
        exit(0)
print('Yes')

Submission Info

Submission Time
Task D - Unicyclic Components
User shinever
Language PyPy3 (7.3.0)
Score 400
Code Size 918 Byte
Status AC
Exec Time 509 ms
Memory 89928 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 61
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 02_one_00.txt, 02_one_01.txt, 02_one_02.txt, 02_one_03.txt, 02_one_04.txt, 02_one_05.txt, 02_one_06.txt, 02_one_07.txt, 02_one_08.txt, 02_one_09.txt, 02_one_10.txt, 02_one_11.txt, 02_one_12.txt, 02_one_13.txt, 03_two_00.txt, 03_two_01.txt, 03_two_02.txt, 03_two_03.txt, 03_two_04.txt, 03_two_05.txt, 03_two_06.txt, 03_two_07.txt, 03_two_08.txt, 03_two_09.txt, 03_two_10.txt, 03_two_11.txt, 04_many_00.txt, 04_many_01.txt, 04_many_02.txt, 04_many_03.txt, 04_many_04.txt, 04_many_05.txt, 04_many_06.txt, 04_many_07.txt, 04_many_08.txt, 04_many_09.txt, 04_many_10.txt, 04_many_11.txt, 05_hand_00.txt, 05_hand_01.txt, 99_hack_00.txt, 99_hack_01.txt, 99_hack_02.txt, 99_hack_03.txt, 99_hack_04.txt, 99_hack_05.txt, 99_hack_06.txt, 99_hack_07.txt, 99_hack_08.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 61 ms 62032 KiB
00_sample_01.txt AC 47 ms 61916 KiB
00_sample_02.txt AC 50 ms 62232 KiB
01_rnd_00.txt AC 48 ms 61896 KiB
01_rnd_01.txt AC 54 ms 62748 KiB
01_rnd_02.txt AC 254 ms 74496 KiB
01_rnd_03.txt AC 48 ms 61836 KiB
01_rnd_04.txt AC 50 ms 62856 KiB
01_rnd_05.txt AC 273 ms 74464 KiB
01_rnd_06.txt AC 62 ms 80808 KiB
01_rnd_07.txt AC 62 ms 81652 KiB
01_rnd_08.txt AC 509 ms 89288 KiB
02_one_00.txt AC 48 ms 62012 KiB
02_one_01.txt AC 49 ms 62116 KiB
02_one_02.txt AC 51 ms 62092 KiB
02_one_03.txt AC 49 ms 61820 KiB
02_one_04.txt AC 48 ms 62108 KiB
02_one_05.txt AC 48 ms 61932 KiB
02_one_06.txt AC 48 ms 61996 KiB
02_one_07.txt AC 381 ms 89448 KiB
02_one_08.txt AC 393 ms 89648 KiB
02_one_09.txt AC 378 ms 89916 KiB
02_one_10.txt AC 383 ms 89776 KiB
02_one_11.txt AC 380 ms 89444 KiB
02_one_12.txt AC 405 ms 89648 KiB
02_one_13.txt AC 379 ms 89508 KiB
03_two_00.txt AC 380 ms 89528 KiB
03_two_01.txt AC 390 ms 89928 KiB
03_two_02.txt AC 374 ms 89692 KiB
03_two_03.txt AC 399 ms 89660 KiB
03_two_04.txt AC 401 ms 89860 KiB
03_two_05.txt AC 383 ms 89564 KiB
03_two_06.txt AC 369 ms 89576 KiB
03_two_07.txt AC 372 ms 89652 KiB
03_two_08.txt AC 375 ms 89688 KiB
03_two_09.txt AC 370 ms 89528 KiB
03_two_10.txt AC 374 ms 89312 KiB
03_two_11.txt AC 381 ms 89800 KiB
04_many_00.txt AC 237 ms 85692 KiB
04_many_01.txt AC 248 ms 85560 KiB
04_many_02.txt AC 245 ms 85848 KiB
04_many_03.txt AC 242 ms 85644 KiB
04_many_04.txt AC 380 ms 89648 KiB
04_many_05.txt AC 381 ms 89684 KiB
04_many_06.txt AC 378 ms 89656 KiB
04_many_07.txt AC 393 ms 89644 KiB
04_many_08.txt AC 380 ms 89424 KiB
04_many_09.txt AC 384 ms 89260 KiB
04_many_10.txt AC 376 ms 89560 KiB
04_many_11.txt AC 380 ms 89316 KiB
05_hand_00.txt AC 48 ms 62128 KiB
05_hand_01.txt AC 294 ms 89924 KiB
99_hack_00.txt AC 50 ms 62008 KiB
99_hack_01.txt AC 51 ms 62108 KiB
99_hack_02.txt AC 51 ms 61972 KiB
99_hack_03.txt AC 51 ms 61828 KiB
99_hack_04.txt AC 50 ms 62172 KiB
99_hack_05.txt AC 49 ms 62180 KiB
99_hack_06.txt AC 51 ms 61956 KiB
99_hack_07.txt AC 52 ms 61960 KiB
99_hack_08.txt AC 46 ms 62136 KiB