from collections import deque

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

# --- BFS (Breadth-First Search) : parcours en largeur, avec une FILE ---
# Garantit le plus court chemin en NOMBRE D'ARÊTES sur un graphe non pondéré
def bfs(graphe: dict, depart: str) -> list[str]:
    visites = {depart}
    file = deque([depart])
    ordre = []
    while file:
        sommet = file.popleft()
        ordre.append(sommet)
        for voisin in graphe.get(sommet, []):
            if voisin not in visites:
                visites.add(voisin)   # marquer visité DÈS l'ajout en file, pas à l'extraction
                file.append(voisin)
    return ordre

assert bfs(graphe, "A") == ["A", "B", "C", "D", "E", "F"]

# BFS pour le plus court chemin (non pondéré) avec reconstruction du chemin
def plus_court_chemin_bfs(graphe: dict, depart: str, arrivee: str) -> list[str] | None:
    if depart == arrivee:
        return [depart]
    visites = {depart}
    file = deque([depart])
    parent = {depart: None}
    while file:
        sommet = file.popleft()
        for voisin in graphe.get(sommet, []):
            if voisin not in visites:
                visites.add(voisin)
                parent[voisin] = sommet
                if voisin == arrivee:
                    # reconstruire le chemin en remontant les parents
                    chemin = [arrivee]
                    while parent[chemin[-1]] is not None:
                        chemin.append(parent[chemin[-1]])
                    return chemin[::-1]
                file.append(voisin)
    return None   # aucun chemin trouvé

assert plus_court_chemin_bfs(graphe, "A", "F") == ["A", "C", "F"]

# --- DFS (Depth-First Search) récursif : parcours en profondeur ---
def dfs_recursif(graphe: dict, sommet: str, visites: set | None = None, ordre: list | None = None) -> list[str]:
    if visites is None:
        visites, ordre = set(), []
    visites.add(sommet)
    ordre.append(sommet)
    for voisin in graphe.get(sommet, []):
        if voisin not in visites:
            dfs_recursif(graphe, voisin, visites, ordre)
    return ordre

assert dfs_recursif(graphe, "A") == ["A", "B", "D", "E", "F", "C"]

# --- DFS itératif avec une pile explicite (évite la limite de récursion sur grands graphes) ---
def dfs_iteratif(graphe: dict, depart: str) -> list[str]:
    visites = set()
    pile = [depart]
    ordre = []
    while pile:
        sommet = pile.pop()
        if sommet not in visites:
            visites.add(sommet)
            ordre.append(sommet)
            # inverser pour visiter les voisins dans le même ordre que la version récursive
            for voisin in reversed(graphe.get(sommet, [])):
                if voisin not in visites:
                    pile.append(voisin)
    return ordre

# --- Détecter les composantes connexes d'un graphe non orienté ---
def composantes_connexes(graphe: dict) -> list[list[str]]:
    visites = set()
    composantes = []
    for sommet in graphe:
        if sommet not in visites:
            composante = dfs_recursif(graphe, sommet, visites, [])
            composantes.append(composante)
    return composantes

# --- Détecter un cycle dans un graphe ORIENTÉ (3 couleurs : blanc/gris/noir) ---
def a_un_cycle_oriente(graphe: dict) -> bool:
    BLANC, GRIS, NOIR = 0, 1, 2
    couleur = {sommet: BLANC for sommet in graphe}

    def visiter(sommet) -> bool:
        couleur[sommet] = GRIS   # en cours de visite (sur la pile d'appels actuelle)
        for voisin in graphe.get(sommet, []):
            if couleur.get(voisin, BLANC) == GRIS:
                return True       # arête vers un sommet EN COURS de visite -> cycle
            if couleur.get(voisin, BLANC) == BLANC and visiter(voisin):
                return True
        couleur[sommet] = NOIR   # visite terminée, définitivement sûr
        return False

    return any(visiter(s) for s in graphe if couleur[s] == BLANC)

graphe_cyclique = {"A": ["B"], "B": ["C"], "C": ["A"]}
assert a_un_cycle_oriente(graphe_cyclique) is True

# --- Tri topologique (DFS) : ordonner les sommets d'un DAG (graphe orienté acyclique) ---
def tri_topologique(graphe: dict) -> list[str]:
    visites = set()
    pile_resultat = []

    def visiter(sommet):
        visites.add(sommet)
        for voisin in graphe.get(sommet, []):
            if voisin not in visites:
                visiter(voisin)
        pile_resultat.append(sommet)   # ajouté APRÈS avoir visité tous ses successeurs

    for sommet in graphe:
        if sommet not in visites:
            visiter(sommet)
    return pile_resultat[::-1]   # inverser : les "sources" doivent apparaître en premier

dag = {"habillage": ["chaussures"], "sous_vetements": ["habillage"], "chaussures": []}
assert tri_topologique(dag) == ["sous_vetements", "habillage", "chaussures"]