Buggy python submission (verdict: Time Limit Exceeded):


def dfs(graph,s):
    visited=[s]
    S=[s]
    while len(S)>0:
        v=S.pop(0)
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                S.append(w)
    return visited

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    adj={i+1:[] for i in range(N)}
    for l in LIST:
        x,y,z=l[0],l[1],l[2]
        if x not in adj[y]:
            adj[y].append(x)
        if y not in adj[x]:
            adj[x].append(y)
    connected=[]
    count=0

    for i in range(1,N+1):
        if i in connected:
            continue
        else:
            connected+=dfs(adj,i)
            count+=1

    print(count)


Fixed submission:




class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n

    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 union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        elif self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x):
        return -self.parents[self.find(x)]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def members(self,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.menbers(r) for r in self.roots()}

    def __str__(self):
        return " \n".join('{}:{}'.format(r,self.members(r)) for r in self.roots())

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFind(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)

    print(union_find.group_count())

Buggy python submission (verdict: Time Limit Exceeded):


def dfs(graph,s):
    visited=[s]
    S=[s]
    while len(S)>0:
        v=S.pop(0)
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                S.append(w)
    return visited

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    adj={i+1:[] for i in range(N)}
    for l in LIST:
        x,y,z=l[0],l[1],l[2]
        if x not in adj[y]:
            adj[y].append(x)
        if y not in adj[x]:
            adj[x].append(y)
    connected=[]
    count=0

    for i in range(1,N+1):
        if i in connected:
            continue
        else:
            connected+=dfs(adj,i)
            count+=1

    print(count)


Fixed submission:




class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n

    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 union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        elif self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x):
        return -self.parents[self.find(x)]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def members(self,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.menbers(r) for r in self.roots()}

    def __str__(self):
        return " \n".join('{}:{}'.format(r,self.members(r)) for r in self.roots())

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFind(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)

    print(union_find.group_count())