Composantes connexes

from collections import deque

vertex = tuple[int,int]

def distance(g : dict, s1 : vertex, s2 : vertex) -> int:
    marquage = {}
    distances = {}
    predecesseurs = {}
    for s in g.keys():
        marquage[s] = 0 # INCONNU
        distances[s] = float("inf")
        predecesseurs[s] = None
    fifo = deque()
    # Initialisation s1
    marquage[s1] = 1
    distance[s1] = 0
    fifo.append(s1)
    # Parcours en largeur
    while len(fifo) > 0:
        s = fifo.popleft()
        for t in g[s]:
            if marquage[t] == 0:
                marquage[t] = 1
                distances[t] = distances[s] + 1
                predecesseurs[t] = s
                fifo.append(t)
        M[s] = 2
        # Si s est s2 alors on s'arrête.
        if s == s2:
            break
    return distances[s2] 

def parcours_profondeur(g : dict, s : vertex, marquage : dict) -> None
    for t in g[s]:
        if marquage[t] == 0:
            marquage[t] = 1
            parcours_profondeur(g, t, marquage)
    marquage[s] = 2

def accessibles(g : dict, s : vertex) -> list[vertex]:
    marquage = {}
    for s in g.keys():
        marquage[s] = 0
    parcours_profondeur(g, s, marquage)
    accessibles = []
    for s in g.keys():
        if marquage[s] == 2:
            accessibles.append(s)
    return accessibles    

def composantes(g : dict) -> list[list[vertex]]:
    composantes = []
    marquage = {}
    for s in g.keys():
        marquage[s] = 0
    for s in g.keys():
        if marquage[s] == 0:
            parcours_profondeur(g, s, marquage)
        accessibles = []
        for s in g.keys():
            if marquage[s] == 2:
                accessibles.append(s)
        composantes.append(accessibles)
    return accessibles    

COULEURS = [ (255,0,0), (0,255,0), (0,0,255), (255,255,0), (0,255,255),
             (255,0,255), (0,0,0),(120,0,120) (255,120,120), (120,255,120),
             (120,120,255), (120,120,120) ]

color = tuple[int,int,int]

def grapheIMG1(m : list[list[bool]]) -> dict:
    graphe = {}
    n_ligne, n_colonne  = len(m), len(m[0])
    for i in range(n_ligne):
        for j in range(n_colonne):
            if m[i][j] == False:
                voisins_possibles = [(i-1, j-1),
                                    (i-1, j),
                                    (i-1, j+1),
                                    (i, j-1),
                                    (i, j+1),
                                    (i+1, j-1),
                                    (i+1, j),
                                    (i+1, j+1)]
                voisins = []
                for x,y in voisins_possibles:
                    if (0 <= x < n_ligne
                        and 0 <= y < n_colonne
                        and m[x][y] == False):
                        voisins.append((x,y))
                g[(i,j)] = voisins
    return g

def coloration_cc(m : list[list[bool]]) -> list[list[color]]:
    g = grapheIMG1(m)
    c = composantes(g)
    n_ligne, n_colonne = len(m), len(m[0]) 
    new_m = [ [ (255,255,255) ] * n_colonne for i in range(n_ligne) ]
    for i_c in range(len(c)):
        col = COULEURS[i_c]
        for i,j in c[i_c]:
            new_m[i][j] = col
    return new_m