Участник:Gadaevtamaz/Number of Connected Components in an Undirected Graph

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(vert):
            seen.add(vert)            
            for neighbour in verts[vert]:
                if neighbour not in seen:
                    dfs(neighbour)
        verts = {i: [] for i in range(n)}
        for a, b in edges:
            verts[a].append(b)
            verts[b].append(a)
        seen = set()
        count = 0 
        for vert in verts:
            if vert not in seen:
                count += 1
                dfs(vert)
        return count