Composantes fortement connexes
Regrouper avec Tarjan les nœuds mutuellement accessibles
Composantes fortement connexes est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Définition d’une SCC
Une composante fortement connexe est un groupe maximal de nœuds où chaque nœud peut atteindre tous les autres en suivant les arêtes orientées.
Pourquoi cela nous intéresse
Réduire chaque SCC à un supernœud transforme tout graphe orienté en DAG. Les dépendances mutuelles deviennent ainsi faciles à analyser.
Tarjan en une seule passe
L’algorithme de Tarjan trouve toutes les SCC en un seul DFS. Il s’exécute en O(V + E), soit le même coût qu’un parcours classique.
Numéros de découverte
Attribuez à chaque nœud un instant de découverte correspondant à l’ordre dans lequel DFS le visite pour la première fois. Ces identifiants permettent de comparer les nœuds vus le plus tôt.
disc = [-1] * n
timer = 0La valeur de liaison basse
La valeur de liaison basse d’un nœud est le plus petit identifiant de découverte accessible depuis celui-ci, y compris en passant par des arêtes de retour. Elle sert de repère pour la composante.
low = [-1] * nEmpiler sur la pile
Lorsque DFS entre dans un nœud, définissez son disc et son low, puis empilez-le dans une pile de nœuds susceptibles d’appartenir à sa composante.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueMettre à jour low à partir des enfants
Après être descendu récursivement dans un enfant non visité, faites remonter sa valeur low : low[u] devient le minimum entre sa valeur actuelle et le low de l’enfant.
dfs(v)
low[u] = min(low[u], low[v])Gérer les arêtes de retour
Si un voisin est déjà dans la pile, c’est un ancêtre de cette SCC. Utilisez son disc pour réduire low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Repérer la racine d’une composante
Lorsque low[u] est égal à disc[u], le nœud u est la racine d’une SCC. Tous les nœuds situés au-dessus de lui dans la pile appartiennent à la même composante.
Extraire la composante
À une racine, appliquez pop aux nœuds de la pile jusqu’à retirer u. Le groupe extrait constitue exactement une composante fortement connexe.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju comme solution alternative
Vous préférez deux passes ? Kosaraju exécute DFS, inverse toutes les arêtes, puis effectue un second DFS dans l’ordre de terminaison pour extraire les SCC.
Vérification rapide
Pendant le DFS de Tarjan, le nœud u vérifie low[u] == disc[u]. Qu’est-ce que cela vous indique ?
Récapitulatif : les SCC avec Tarjan
Suivez disc et low dans un seul DFS, empilez les nœuds actifs et extrayez une composante dès que low est égal à disc. Des SCC en O(V+E). 🧩
Questions Fréquemment Posées
La leçon « Composantes fortement connexes » est-elle gratuite ?
Oui — le texte complet de « Composantes fortement connexes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Composantes fortement connexes » ?
Regrouper avec Tarjan les nœuds mutuellement accessibles Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Composantes fortement connexes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri topologique avec l’algorithme de Kahn
- Détecter les cycles dans les graphes orientés
- Composantes fortement connexes
- Ponts et points d’articulation