Submission #8886080

---

Source Code Expand

def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index][0]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index][0]
            for i in temp_list:
                self.tree[i][0]=index
            return index
        
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
 
    u=unionfind(n)
    for a,b in ab:
        u.unite(a-1,b-1)
    print(u.component()-1)

main()

Submission Info

Judge Result