Strongly Connected Components
Un graphe orienté possède n nœuds, numérotés de 0 à n-1, et une liste d’edges, où [from, to] représente une arête du nœud from au nœud to.
Une composante fortement connexe est un plus grand groupe de nœuds dans lequel chaque nœud peut atteindre tous les autres en suivant les arêtes. Chaque nœud appartient à exactement une composante, et un nœud qui ne se trouve sur aucun cycle forme une composante à lui seul. Retournez le nombre de composantes fortement connexes.
Fonction
- ninteger
- le nombre de nœuds
- edgesinteger-2d-array
- les arêtes orientées, chacune sous la forme [from, to]
- Renvoieinteger
- le nombre de composantes fortement connexes
Contraintes
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]avec0 ≤ from, to < netfrom ≠ to- Aucune arête n’apparaît deux fois.
Exemples
- Entrée
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Sortie
- 3
- Explication
- Les nœuds 0, 1 et 2 forment une boucle, ils peuvent donc s’atteindre mutuellement. Les nœuds 3 et 4 pointent l’un vers l’autre. Le nœud 5 atteint le nœud 4, mais rien ne revient vers le nœud 5, il reste donc isolé : 3 composantes.
- Entrée
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Sortie
- 4
- Explication
- Les nœuds 0 et 1 pointent l’un vers l’autre et forment une composante. L’arête de 2 à 3 ne va que dans un seul sens, donc 2 et 3 sont séparés, et le nœud 4 n’a aucune arête : 4 composantes.
Pour aller plus loin
Combien d’arêtes au minimum faudrait-il ajouter pour que le graphe entier forme une seule composante fortement connexe ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Deux nœuds partagent une composante exactement lorsque chacun peut atteindre l’autre. Une recherche à partir de chaque nœud peut le vérifier, mais elle parcourt les mêmes arêtes encore et encore. Que peut vous apprendre une seule recherche en profondeur sur l’endroit où commence une composante ?
Numérotez les nœuds dans l’ordre où un parcours en profondeur les atteint pour la première fois. Pour chaque nœud, suivez également
low: le plus petit numéro qu’il peut atteindre en descendant dans l’arbre de recherche, puis en suivant une arête de retour vers un nœud dont la composante est encore ouverte. Un nœud dontlowest égal à son propre numéro est le premier nœud de sa composante.Gardez les nœuds visités sur une pile. Lorsqu’un nœud termine avec
lowégal à son propre numéro, dépilez jusqu’à ce nœud : ces nœuds forment une composante, comptez-la. Un test fait descendre la recherche à une profondeur de 5000 nœuds ; utilisez donc votre propre pile de cadres (nœud, arête suivante) au lieu de recourir à la récursion.
Solution
Réduisez chaque composante à un point, et les composantes forment un graphe sans cycles. Les algorithmes de Kosaraju et de Tarjan utilisent cela pour trouver chaque composante en O(n + E), où E est le nombre d’arêtes.
Rechercher vers l’avant et vers l’arrière à partir de chaque nœud
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Les nœuds u et v appartiennent à la même composante exactement lorsque chacun peut atteindre l’autre. Donc, pour un nœud s qui n’appartient encore à aucune composante, effectuez une recherche vers l’avant le long des arêtes et une recherche vers l’arrière le long des arêtes inversées. Les nœuds trouvés par les deux recherches forment sa composante. Dans le premier exemple, la recherche vers l’avant à partir de 0 trouve les nœuds de 0 à 4, et la recherche vers l’arrière trouve 0, 1 et 2 : {0, 1, 2} forme donc une composante.
Chaque composante nécessite deux recherches dans la majeure partie du graphe. Sur une chaîne de 5000 arêtes reliant 5001 nœuds, chaque nœud forme sa propre composante, et les recherches parcourent environ 2.5 × 10^7 nœuds.
Algorithme
- Construisez les listes des arêtes sortantes et entrantes de chaque nœud.
- Prenez le prochain nœud
ssans composante et comptez une nouvelle composante. - Marquez les nœuds que
satteint en suivant les arêtes sortantes, ainsi que ceux qui l’atteignent en suivant les arêtes entrantes. - Chaque nœud marqué par les deux recherches rejoint la composante de
s. Lorsque chaque nœud en a une, renvoyez le nombre.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countAlgorithme de Kosaraju : deux passes
Intuition
Dans le graphe des composantes, une composante est un puits, sans arête sortante, et une recherche commencée à l’intérieur de celle-ci ne trouve que cette composante. L’algorithme de Kosaraju ordonne les recherches de sorte que chacune se comporte ainsi.
La première passe répertorie chaque nœud lorsque son parcours en profondeur se termine. La deuxième passe explore le graphe inversé, qui possède les mêmes composantes, en commençant par le dernier nœud à terminer. Si une arête mène de la composante B à C, le dernier nœud de B termine après tous ceux de C. Ainsi, lorsque la deuxième passe atteint C, toutes les composantes ayant une arête vers C sont déjà assignées, et, dans le graphe inversé, la recherche ne peut pas quitter C.
Dans le premier exemple, les nœuds terminent dans l’ordre 4, 3, 2, 1, 0, 5. La deuxième passe recueille {5}, puis {0, 1, 2}, puis {3, 4}.
Algorithme
- Construis les listes d’arêtes sortantes et entrantes.
- Lance une recherche en profondeur itérative depuis chaque nœud non visité, et ajoute chaque nœud à
orderlorsqu’il est terminé. - Parcours
orderen partant de la fin. Pour chaque nœud qui n’appartient pas à une composante, incrémente le compteur et lance une recherche depuis ce nœud en suivant les arêtes entrantes, en attribuant une composante à chaque nœud non attribué atteint. Retourne le compteur.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countAlgorithme de Tarjan : un seul parcours avec des valeurs low
Intuition
Effectuez une seule recherche en profondeur et attribuez un numéro à chaque nœud dans l’ordre où vous l’atteignez : son index. Gardez une pile des nœuds visités dont la composante est encore ouverte, ainsi qu’une valeur low : le plus petit index qu’un nœud peut atteindre en descendant dans l’arbre de recherche, puis en empruntant une arête vers un nœud de cette pile.
Quand l’exploration d’un nœud se termine avec low inférieur à index, cela signifie qu’un nœud situé plus bas remonte jusqu’à un nœud ouvert antérieur ; le nœud reste donc sur la pile. Quand ils sont égaux, le nœud est le premier que la recherche a atteint dans sa composante : dépilez jusqu’à lui et comptez une composante. Une arête vers un nœud dépilé mène à une composante terminée qui ne peut pas remonter ; elle est donc ignorée.
Dans le premier exemple, 3 dépile {4, 3} et 0 dépile {2, 1, 0}. L’arête du nœud 5 mène au nœud 4, qui a été dépilé ; 5 est donc dépilé seul.
Algorithme
- Pour chaque nœud non visité, attribuez-lui l’index suivant, définissez
lowsur la même valeur, empilez-le sur la pile des nœuds et empilez le cadre (node, first edge). - Si le nœud du cadre supérieur a encore une arête à parcourir, suivez-la : une cible non visitée reçoit un index et un cadre, et une cible présente sur la pile des nœuds fait diminuer
low[node]jusqu’à son index. - Sinon, dépilez le cadre et faites diminuer le
lowdu parent jusqu’àlow[node]. Silow[node]est égal àindex[node], dépilez la pile des nœuds jusqu’au nœud et comptez une composante.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Pièges et cas limites
- Oublier les nœuds sans arêtes. Dans le deuxième exemple, le nœud 4 n’apparaît dans aucune arête et constitue tout de même une composante.
- Abaisser
lowà travers n’importe quel nœud visité au lieu de ne le faire qu’à travers ceux qui sont dans la pile. Dans le premier exemple, l’arête5 → 4empêche alors 5 de fermer sa composante. - Traiter les arêtes comme étant à double sens. Cela permet de compter les composantes connexes : le premier exemple donnerait 1 au lieu de 3.
- Utiliser la récursion en Python. Un cycle de 5000 nœuds entraîne 5000 appels imbriqués, soit cinq fois la limite par défaut de 1000. Gardez votre propre pile de cadres d’appel.
- Exécuter la deuxième passe de Kosaraju sur les arêtes d’origine, ou dans l’ordre de première visite des nœuds. Dans les deux cas, des composantes qui ne peuvent s’atteindre que dans un seul sens sont fusionnées.
Questions fréquentes3
Quelle est la complexité temporelle de la recherche des composantes fortement connexes ?
Temps O(n + E) avec l’algorithme de Kosaraju ou de Tarjan, puisque chaque nœud et chaque arête sont traités un nombre constant de fois. Les deux utilisent un espace O(n + E) pour les listes d’arêtes et les piles de recherche.
Faut-il utiliser l’algorithme de Kosaraju ou celui de Tarjan ?
L’algorithme de Kosaraju consiste en deux parcours simples et est plus difficile à mal implémenter. Celui de Tarjan n’en nécessite qu’un et ne requiert pas de graphe inversé, au prix de la gestion de low.
Quelle est la différence entre les composantes fortement connexes et les composantes connexes ?
Les composantes connexes ignorent le sens des arêtes : deux nœuds sont connectés lorsqu’un chemin les relie. Dans une composante fortement connexe, chaque nœud doit pouvoir atteindre l’autre. Le premier exemple forme une seule composante connexe, mais trois composantes fortement connexes.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def countSCC(n, edges):
# Écrivez le code iciTest #1
Test #2
Arguments
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Résultat attendu
3