Submission #17027498


Source Code Expand

Copy
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ?
        return self.find(x)==self.find(y)
    def members(self,x):
        #xと同じグループに属する要素のリスト
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

def main():
    n, m = map(int,input().split())
    AB_union = UnionFind(n)
    for i in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        AB_union.unite(a, b)
    print(AB_union.group_count() - 1)



if __name__=='__main__':
    main()

Submission Info

Submission Time
Task C - Connect Cities
User charter
Language Python (3.8.2)
Score 300
Code Size 2305 Byte
Status
Exec Time 225 ms
Memory 12960 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
× 1
× 21
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, example0.txt
Case Name Status Exec Time Memory
000.txt 132 ms 9260 KB
001.txt 63 ms 9240 KB
002.txt 62 ms 11120 KB
003.txt 187 ms 9372 KB
004.txt 196 ms 9456 KB
005.txt 101 ms 11156 KB
006.txt 193 ms 10372 KB
007.txt 34 ms 12960 KB
008.txt 211 ms 10780 KB
009.txt 98 ms 9336 KB
010.txt 219 ms 11188 KB
011.txt 221 ms 11008 KB
012.txt 220 ms 10876 KB
013.txt 221 ms 10876 KB
014.txt 218 ms 11060 KB
015.txt 225 ms 11008 KB
016.txt 218 ms 10980 KB
017.txt 220 ms 11188 KB
018.txt 223 ms 11044 KB
019.txt 223 ms 11180 KB
example0.txt 20 ms 9172 KB