Compter les composantes connexes

On lance un parcours à partir de chaque sommet non encore visité ; chaque parcours révèle une composante entière.

def nb_composantes(G):
    visites = set()
    nb = 0

    def explorer(depart):
        pile = [depart]
        while pile:
            u = pile.pop()
            if u not in visites:
                visites.add(u)
                for v in G[u]:
                    if v not in visites:
                        pile.append(v)

    for sommet in G:
        if sommet not in visites:
            nb += 1
            explorer(sommet)
    return nb

G = {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3]}
print(nb_composantes(G))   # 2

La complexité est $O(n+m)$ : chaque sommet et chaque lien sont traités une seule fois au total.