Algorithmes
Avancés

# O(1) — accès direct, peu importe n
def premier(lst):
    return lst[0]

# O(n) — une passe sur la liste
def somme(lst):
    total = 0
    for x in lst:
        total += x
    return total

# O(n²) — boucles imbriquées
def paires_doublons(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                print(lst[i], lst[j])

# O(n) avec dict — la même chose en mieux !
def paires_doublons_v2(lst):
    vus = set()
    for x in lst:
        if x in vus:
            print(x)
        vus.add(x)

def quicksort(arr: list, g: int = 0, d: int = None) -> None:
    if d is None: d = len(arr) - 1
    if g >= d: return

    pivot_pos = _partitionner(arr, g, d)
    quicksort(arr, g, pivot_pos - 1)
    quicksort(arr, pivot_pos + 1, d)

def _partitionner(arr, g, d):
    pivot = arr[d]
    i = g - 1
    for j in range(g, d):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[d] = arr[d], arr[i + 1]
    return i + 1

# Version fonctionnelle (plus lisible, O(n) mémoire)
def qs(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr) // 2]
    gauche  = [x for x in arr if x <  pivot]
    milieu  = [x for x in arr if x == pivot]
    droite  = [x for x in arr if x >  pivot]
    return qs(gauche) + milieu + qs(droite)

arr = [3, 6, 8, 10, 1, 2, 1]
print(qs(arr))  # [1, 1, 2, 3, 6, 8, 10]

def mergesort(arr: list) -> list:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    gauche = mergesort(arr[:mid])
    droite = mergesort(arr[mid:])
    return _fusionner(gauche, droite)

def _fusionner(gauche: list, droite: list) -> list:
    resultat = []
    i = j = 0

    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1

    # Ajouter les éléments restants
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

arr = [38, 27, 43, 3, 9, 82, 10]
print(mergesort(arr))
# [3, 9, 10, 27, 38, 43, 82]

def heapify(arr, n, i):
    """Maintenir la propriété max-heap à partir de i."""
    plus_grand = i
    gauche  = 2 * i + 1
    droite  = 2 * i + 2

    if gauche < n and arr[gauche] > arr[plus_grand]:
        plus_grand = gauche
    if droite < n and arr[droite] > arr[plus_grand]:
        plus_grand = droite

    if plus_grand != i:
        arr[i], arr[plus_grand] = arr[plus_grand], arr[i]
        heapify(arr, n, plus_grand)  # récursif vers le bas

def heapsort(arr):
    n = len(arr)
    # Phase 1 : construire le max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Phase 2 : extraire les maximums un par un
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # max → fin
        heapify(arr, i, 0)               # restaurer le heap

# Python — heapq (min-heap natif)
import heapq
arr = [3, 1, 4, 1, 5]
heapq.heapify(arr)           # O(n)
min_val = heapq.heappop(arr) # O(log n)

# Itératif — préférable (pas de pile d'appels)
def recherche_binaire(arr: list, cible) -> int:
    g, d = 0, len(arr) - 1
    while g <= d:
        m = (g + d) // 2
        if   arr[m] == cible: return m
        elif arr[m] <  cible: g = m + 1
        else:                 d = m - 1
    return -1

# Module bisect — recherche binaire en Python std
import bisect
arr = [1, 3, 5, 7, 9, 11]
i = bisect.bisect_left(arr, 7)   # → 3
# bisect_left  : position d'insertion à gauche
# bisect_right : position d'insertion à droite

# Application : trouver le plus proche
def plus_proche(arr, cible):
    i = bisect.bisect_left(arr, cible)
    if i == 0: return arr[0]
    if i == len(arr): return arr[-1]
    if arr[i] - cible < cible - arr[i-1]:
        return arr[i]
    return arr[i - 1]

# Graphe non orienté :
#   A — B — D
#   |   |
#   C — E

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

# Graphe pondéré (avec poids sur les arêtes) :
graphe_pondere = {
    "A": {"B": 4, "C": 2},
    "B": {"A": 4, "D": 5, "E": 1},
    "C": {"A": 2, "E": 3},
    "D": {"B": 5},
    "E": {"B": 1, "C": 3},
}

from collections import deque

def bfs(graphe: dict, depart: str) -> list:
    """Retourne l'ordre de visite des nœuds."""
    visite = {depart}
    file = deque([depart])
    ordre = []

    while file:
        noeud = file.popleft()  # O(1) avec deque
        ordre.append(noeud)
        for voisin in graphe[noeud]:
            if voisin not in visite:
                visite.add(voisin)
                file.append(voisin)
    return ordre

def chemin_bfs(graphe, depart, arrivee):
    """Plus court chemin (arêtes) entre deux nœuds."""
    predecesseur = {depart: None}
    file = deque([depart])

    while file:
        noeud = file.popleft()
        if noeud == arrivee:
            break
        for v in graphe[noeud]:
            if v not in predecesseur:
                predecesseur[v] = noeud
                file.append(v)

    # Reconstruire le chemin à rebours
    chemin, noeud = [], arrivee
    while noeud is not None:
        chemin.append(noeud)
        noeud = predecesseur.get(noeud)
    return chemin[::-1]

def dfs(graphe, noeud, visite=None):
    if visite is None: visite = set()
    visite.add(noeud)
    print(noeud)
    for v in graphe[noeud]:
        if v not in visite:
            dfs(graphe, v, visite)

# Détection de cycle dans un graphe orienté
def a_un_cycle(graphe) -> bool:
    blanc = set(graphe)   # non visité
    gris  = set()         # en cours de visite
    noir  = set()         # terminé

    def dfs_cycle(n):
        blanc.discard(n)
        gris.add(n)
        for v in graphe.get(n, []):
            if v in gris: return True   # cycle !
            if v in blanc and dfs_cycle(v): return True
        gris.discard(n); noir.add(n)
        return False

    return any(dfs_cycle(n) for n in list(blanc))

import heapq

def dijkstra(graphe: dict, depart: str) -> dict:
    """
    graphe = {"A": {"B": 4, "C": 2}, ...}
    Retourne distances minimales depuis depart.
    """
    dist = {n: float("inf") for n in graphe}
    dist[depart] = 0
    precedent = {n: None for n in graphe}
    heap = [(0, depart)]  # (coût, nœud)

    while heap:
        cout, noeud = heapq.heappop(heap)
        if cout > dist[noeud]:
            continue  # entrée obsolète
        for voisin, poids in graphe[noeud].items():
            nd = dist[noeud] + poids
            if nd < dist[voisin]:
                dist[voisin] = nd
                precedent[voisin] = noeud
                heapq.heappush(heap, (nd, voisin))

    return dist, precedent

# Reconstruire le chemin
def reconstruire(precedent, arrivee):
    chemin = []
    while arrivee:
        chemin.append(arrivee)
        arrivee = precedent[arrivee]
    return chemin[::-1]

import heapq

def heuristique(a, b):
    """Distance de Manhattan — parfaite pour une grille."""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(grille, depart, arrivee):
    """
    grille = liste 2D (0=libre, 1=mur)
    depart, arrivee = (ligne, colonne)
    """
    rows, cols = len(grille), len(grille[0])
    directions = [(0,1),(0,-1),(1,0),(-1,0)]

    g = {depart: 0}          # coût réel depuis depart
    pred = {depart: None}
    heap = [(0 + heuristique(depart, arrivee), depart)]

    while heap:
        f, pos = heapq.heappop(heap)
        if pos == arrivee:
            # Reconstruire le chemin
            chemin = []
            while pos: chemin.append(pos); pos = pred[pos]
            return chemin[::-1]

        for dr, dc in directions:
            voisin = (pos[0]+dr, pos[1]+dc)
            r, c = voisin
            if not (0 <= r < rows and 0 <= c < cols): continue
            if grille[r][c] == 1: continue  # mur
            ng = g[pos] + 1
            if voisin not in g or ng < g[voisin]:
                g[voisin] = ng
                pred[voisin] = pos
                heapq.heappush(heap, (ng + heuristique(voisin, arrivee), voisin))
    return None  # pas de chemin

# Problème : trouver min ET max d'un tableau
# Naïf : 2(n-1) comparaisons
# Diviser pour régner : ~3n/2 comparaisons

def min_max(arr, g, d):
    """Retourne (min, max) de arr[g..d]."""
    # Cas de base
    if g == d:
        return arr[g], arr[g]
    if d - g == 1:
        return (arr[g], arr[d]) if arr[g] < arr[d] else (arr[d], arr[g])

    # Diviser
    m = (g + d) // 2
    min_g, max_g = min_max(arr, g, m)
    min_d, max_d = min_max(arr, m + 1, d)

    # Combiner
    return min(min_g, min_d), max(max_g, max_d)

# Puissance rapide — O(log n) au lieu de O(n)
def puissance(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        moitie = puissance(base, exp // 2)
        return moitie * moitie          # ← diviser
    return base * puissance(base, exp - 1)

# Problème : trouver le sous-tableau contigu
# avec la plus grande somme.
# [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Réponse : [4, -1, 2, 1] → somme = 6

# Kadane — O(n) (approche glissante, plus simple)
def max_sous_tableau(arr):
    max_global = max_courant = arr[0]
    debut = fin = 0
    temp_debut = 0

    for i in range(1, len(arr)):
        if arr[i] > max_courant + arr[i]:
            max_courant = arr[i]
            temp_debut = i
        else:
            max_courant += arr[i]

        if max_courant > max_global:
            max_global = max_courant
            debut, fin = temp_debut, i

    return max_global, arr[debut:fin+1]

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_sous_tableau(arr))  # (6, [4,-1,2,1])

def permutations(elements: list) -> list:
    """Génère toutes les permutations — O(n! × n)."""
    if len(elements) <= 1:
        return [elements]

    resultat = []
    for i, elem in enumerate(elements):
        reste = elements[:i] + elements[i+1:]
        for perm in permutations(reste):
            resultat.append([elem] + perm)
    return resultat

# Équivalent Python :
from itertools import permutations as perms
list(perms([1, 2, 3]))

def n_reines(n: int) -> list[list[int]]:
    """Toutes les solutions pour placer n reines
    sur un échiquier n×n sans qu'elles s'attaquent."""
    solutions = []

    def backtrack(ligne, cols, diag1, diag2, placement):
        if ligne == n:
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols \
            or (ligne - col) in diag1 \
            or (ligne + col) in diag2:
                continue   # ← backtrack ici
            placement.append(col)
            cols.add(col)
            diag1.add(ligne - col)
            diag2.add(ligne + col)
            backtrack(ligne+1, cols, diag1, diag2, placement)
            # Annuler le choix (backtrack)
            placement.pop()
            cols.discard(col)
            diag1.discard(ligne - col)
            diag2.discard(ligne + col)

    backtrack(0, set(), set(), set(), [])
    return solutions

from functools import lru_cache

# Tout problème récursif peut bénéficier de @lru_cache
# si les mêmes appels se répètent avec les mêmes args

# Avant :
def fib_lent(n):
    if n <= 1: return n
    return fib_lent(n-1) + fib_lent(n-2)  # O(2ⁿ)

# Après (une ligne !) :
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)    # O(n) !

# @cache = @lru_cache(maxsize=None) depuis Python 3.9
from functools import cache

@cache
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Problème : pour monter n marches en faisant
# des pas de 1 ou 2, combien de façons différentes ?
# n=1 → 1 façon  (1)
# n=2 → 2 façons (1+1, 2)
# n=3 → 3 façons (1+1+1, 1+2, 2+1)
# n=4 → 5 façons  → c'est Fibonacci !

# Top-down
from functools import cache

@cache
def escalier(n: int) -> int:
    if n <= 2: return n
    return escalier(n - 1) + escalier(n - 2)

# Bottom-up — O(n) temps, O(1) mémoire
def escalier_v2(n: int) -> int:
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# Extension : pas de 1, 2 ou 3 marches
@cache
def escalier3(n: int) -> int:
    if n == 0: return 1
    if n < 0: return 0
    return escalier3(n-1) + escalier3(n-2) + escalier3(n-3)

def sac_a_dos(poids: list, valeurs: list, W: int) -> int:
    """
    Valeur maximale pour une capacité W.
    poids   = [2, 3, 4, 5]
    valeurs = [3, 4, 5, 6]
    W = 5 → valeur max = 7 (objets 0 et 1)
    """
    n = len(poids)
    # dp[i][w] = valeur max avec i premiers objets, capacité w
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # Ne pas prendre l'objet i-1
            dp[i][w] = dp[i-1][w]
            # Le prendre si le poids le permet
            if poids[i-1] <= w:
                avec = dp[i-1][w - poids[i-1]] + valeurs[i-1]
                dp[i][w] = max(dp[i][w], avec)

    return dp[n][W]

def lcs(X: str, Y: str) -> str:
    """Retourne la LCS de X et Y."""
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # match !
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Reconstruire la chaîne
    resultat, i, j = [], m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            resultat.append(X[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(resultat))

X, Y = "ABCBDAB", "BDCAB"
print(lcs(X, Y))   # "BCAB" ou "BDAB" — longueur 4

def edit_distance(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]
print(edit_distance("kitten", "sitting"))  # 3

# Idée : à chaque passe, faire "remonter" le plus grand élément
# comme une bulle qui remonte à la surface.

def tri_bulles(lst):
    n = len(lst)
    for i in range(n - 1):            # n-1 passes
        for j in range(n - 1 - i):    # la fin est déjà triée
            if lst[j] > lst[j + 1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]  # échange
    return lst

# Version optimisée — arrêt si déjà trié
def tri_bulles_v2(lst):
    n = len(lst)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                echange = True
        if not echange:   # aucun échange → déjà trié
            break
    return lst

# Trace sur [5, 3, 8, 1] :
# Passe 1 : [3,5,8,1] → [3,5,8,1] → [3,5,1,8]   fin=8 placé
# Passe 2 : [3,5,1,8] → [3,1,5,8]                fin=5 placé
# Passe 3 : [1,3,5,8]                             terminé

# Idée : trouver le minimum du sous-tableau non trié,
# le placer en tête.

def tri_selection(lst):
    n = len(lst)
    for i in range(n - 1):
        idx_min = i
        for j in range(i + 1, n):
            if lst[j] < lst[idx_min]:
                idx_min = j
        lst[i], lst[idx_min] = lst[idx_min], lst[i]  # 1 seul échange/passe
    return lst

# Avantage : exactement n-1 échanges (utile si l'échange est coûteux)
# Inconvénient : O(n²) même si déjà trié — pas d'optimisation possible

# Idée : construire le tableau trié élément par élément,
# comme on trie des cartes à la main.

def tri_insertion(lst):
    for i in range(1, len(lst)):
        cle = lst[i]       # l'élément à insérer
        j = i - 1
        while j >= 0 and lst[j] > cle:
            lst[j + 1] = lst[j]   # décaler vers la droite
            j -= 1
        lst[j + 1] = cle          # insérer à la bonne position
    return lst

# Trace sur [5, 3, 8, 1] :
# i=1 : clé=3, décaler 5 → [5,5,8,1] → insérer → [3,5,8,1]
# i=2 : clé=8, 8>5 ? non → [3,5,8,1]
# i=3 : clé=1, décaler 8,5,3 → insérer → [1,3,5,8]

# Meilleur cas O(n) : tableau déjà trié — aucun décalage
# C'est pourquoi Timsort l'utilise sur les petits blocs !

# DP Fibonacci — O(n) espace → O(1)
def fib_space_optimise(n):
    if n <= 1: return n
    a, b = 0, 1               # seulement 2 variables
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# DP Sac à dos — O(n·W) → O(W)
# Utiliser une seule ligne du tableau (parcours inversé)
def sac_a_dos_optimise(poids, valeurs, W):
    dp = [0] * (W + 1)           # une seule ligne
    for i in range(len(poids)):
        for w in range(W, poids[i] - 1, -1):  # ← parcours inversé !
            dp[w] = max(dp[w], dp[w - poids[i]] + valeurs[i])
    return dp[W]

# Merge sort — trier en place pour O(1) espace
# (plus complexe, mais possible)

# Complexité de la pile de récursion
import sys
sys.getrecursionlimit()   # 1000 par défaut
# Chaque appel récursif occupe de l'espace dans la pile
# DFS récursif sur un graphe de 10 000 nœuds → stack overflow !
# → Convertir en itératif avec une pile explicite

# Rendre la monnaie avec le moins de pièces possible.
# Stratégie gloutonne : toujours prendre la plus grande pièce ≤ montant restant.

# ✓ Optimal pour les systèmes de pièces standards (1, 2, 5, 10, 20, 50...)
# ✗ PAS optimal pour un système arbitraire : pièces [1, 3, 4], montant 6
#    Greedy : 4+1+1 = 3 pièces
#    Optimal : 3+3   = 2 pièces

def rendu_monnaie(montant, pieces):
    pieces_triees = sorted(pieces, reverse=True)
    rendu = []
    for piece in pieces_triees:
        while montant >= piece:
            rendu.append(piece)
            montant -= piece
    return rendu if montant == 0 else None  # None si impossible

print(rendu_monnaie(87, [50, 20, 10, 5, 2, 1]))
# [50, 20, 10, 5, 2]  = 5 pièces

# Sélectionner le maximum d'activités non chevauchantes.
# Stratégie : trier par heure de fin, toujours choisir
# l'activité compatible qui se termine le plus tôt.

def selection_activites(activites):
    # activites = [(debut, fin, nom), ...]
    triees = sorted(activites, key=lambda a: a[1])  # trier par fin
    selectionnees = [triees[0]]
    for debut, fin, nom in triees[1:]:
        if debut >= selectionnees[-1][1]:  # commence après la fin de la dernière
            selectionnees.append((debut, fin, nom))
    return selectionnees

activites = [(1,4,'A'), (3,5,'B'), (0,6,'C'), (5,7,'D'), (8,9,'E')]
print(selection_activites(activites))
# [(1,4,'A'), (5,7,'D'), (8,9,'E')]  — 3 activités max

# Contrairement au sac à dos 0/1, on peut prendre des fractions.
# Stratégie : trier par ratio valeur/poids décroissant.
# ← Greedy donne ici l'optimal garanti !

def sac_fractionnable(items, capacite):
    # items = [(poids, valeur, nom), ...]
    triees = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    valeur_totale = 0.0
    for poids, valeur, nom in triees:
        if capacite >= poids:
            valeur_totale += valeur
            capacite -= poids
        else:
            valeur_totale += valeur * (capacite / poids)
            break
    return valeur_totale

items = [(10, 60, 'Or'), (20, 100, 'Argent'), (30, 120, 'Bronze')]
print(sac_fractionnable(items, 50))  # 240.0

def floyd_warshall(graphe):
    """
    graphe : matrice d'adjacence n×n
    graphe[i][j] = poids de l'arête i→j
                 = float('inf') si pas d'arête
                 = 0            si i == j
    """
    n = len(graphe)
    dist = [row[:] for row in graphe]  # copie
    next_node = [[j if graphe[i][j] != float('inf') else None
                  for j in range(n)] for i in range(n)]

    for k in range(n):          # sommet intermédiaire
        for i in range(n):      # sommet de départ
            for j in range(n):  # sommet d'arrivée
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]  # reconstruire chemin

    # Détecter les cycles négatifs
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError("Cycle négatif détecté !")

    return dist, next_node

def reconstruire_chemin(next_node, i, j):
    if next_node[i][j] is None: return []
    chemin = [i]
    while i != j:
        i = next_node[i][j]
        chemin.append(i)
    return chemin

INF = float('inf')
G = [
    [0,   3,  INF, 7  ],
    [8,   0,  2,  INF],
    [5,   INF, 0,  1  ],
    [2,   INF, INF, 0  ],
]
dist, _ = floyd_warshall(G)
print(dist[0])  # [0, 3, 5, 6]  — depuis le sommet 0

# Est-ce que j est accessible depuis i ?
# Variante booléenne de Floyd-Warshall

def fermeture_transitive(adj):
    n = len(adj)
    atteint = [[adj[i][j] for j in range(n)] for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                atteint[i][j] = atteint[i][j] or (atteint[i][k] and atteint[k][j])
    return atteint

from collections import deque, defaultdict

def tri_topologique_kahn(n, aretes):
    """
    n : nombre de sommets (0..n-1)
    aretes : liste de (u, v) = u doit précéder v
    """
    in_degree = [0] * n
    voisins = defaultdict(list)

    for u, v in aretes:
        voisins[u].append(v)
        in_degree[v] += 1

    # Commencer avec les sommets sans prérequis
    file = deque(i for i in range(n) if in_degree[i] == 0)
    resultat = []

    while file:
        u = file.popleft()
        resultat.append(u)
        for v in voisins[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                file.append(v)

    if len(resultat) != n:
        raise ValueError("Cycle détecté ! Pas un DAG.")
    return resultat

# Exemple : cours avec prérequis
# 0=Maths, 1=Algo, 2=POO, 3=Réseaux, 4=Projet
aretes = [(0,1), (0,2), (1,4), (2,4), (3,4)]
print(tri_topologique_kahn(5, aretes))
# [0, 3, 1, 2, 4] ou [0, 3, 2, 1, 4]
# → Maths et Réseaux d'abord, Projet en dernier

def tri_topo_dfs(n, voisins):
    BLANC, GRIS, NOIR = 0, 1, 2
    couleur = [BLANC] * n
    ordre = []

    def dfs(u):
        couleur[u] = GRIS     # en cours de visite
        for v in voisins.get(u, []):
            if couleur[v] == GRIS:
                raise ValueError("Cycle détecté !")
            if couleur[v] == BLANC:
                dfs(v)
        couleur[u] = NOIR     # traitement terminé
        ordre.append(u)       # ← insérer en fin

    for i in range(n):
        if couleur[i] == BLANC:
            dfs(i)

    return list(reversed(ordre))  # renverser pour l'ordre correct