Composantes fortement connexes
Regrouper avec Tarjan les nœuds mutuellement accessibles
Composantes fortement connexes est une leçon Competitive Programming Academy 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy 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). 🧩
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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