Connexion redondante et détection de cycles
Détectez l’arête qui crée un cycle dans un graphe non orienté en appliquant union à chaque arête et en vérifiant si deux nœuds sont déjà connectés.
Connexion redondante et détection de cycles est une leçon DSA 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’une connexion redondante ?
Le problème de la connexion redondante (LeetCode 684) vous donne un arbre de n nœuds et une arête supplémentaire, formant exactement un cycle. Votre tâche consiste à trouver l’arête qui, une fois supprimée, rétablit l’arbre. Si plusieurs réponses sont possibles, renvoyez la dernière dans la liste d’entrée.
Un arbre de n nœuds possède exactement n-1 arêtes et est connexe, sans cycle. L’ajout d’une arête supplémentaire crée exactement un cycle. L’arête ajoutée (redondante) relie deux nœuds qui appartenaient déjà à la même composante — un cas classique de détection de cycle avec DSU.
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')Détection des cycles avec DSU
DSU détecte naturellement les cycles : avant d’ajouter une arête (u, v), vérifiez si find(u) == find(v). Si les deux nœuds ont la même racine, ils sont déjà reliés — l’ajout de cette arête crée un cycle. Il s’agit de l’arête redondante.
Cette approche fonctionne pour les graphes non orientés. Pour chaque arête, soit nous réussissons à effectuer union des deux composantes (aucun cycle pour le moment), soit nous détectons que les deux extrémités appartiennent déjà à la même composante (cycle détecté). La complexité temporelle est O(n × alpha(n)), soit presque O(n).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]Parcourir l’algorithme étape par étape
Parcourons [[1,2],[1,3],[2,3]] étape par étape. Au départ, chaque nœud constitue sa propre composante : {1}, {2}, {3}.
- Arête [1,2] : find(1)=1, find(2)=2, les racines sont différentes — effectuons union entre elles. Composantes : {1,2}, {3}
- Arête [1,3] : find(1)=racine, find(3)=3, les racines sont différentes — effectuons union entre elles. Composantes : {1,2,3}
- Arête [2,3] : find(2)=racine, find(3)=racine — même racine ! Cycle détecté. Renvoyez [2,3].
L’algorithme traite les arêtes dans l’ordre et renvoie la première arête qui complète un cycle. Comme le problème garantit une seule arête supplémentaire, il s’agit toujours de l’arête redondante correcte.
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)Détection des cycles dans les graphes non orientés avec DFS
Une autre méthode que DSU pour détecter les cycles dans les graphes non orientés est le DFS avec suivi du parent. Pendant le DFS, si nous atteignons un nœud déjà visité qui n’est pas le parent direct du nœud actuel, nous avons trouvé une arête de retour — ce qui indique un cycle.
Cependant, l’approche par DFS nécessite O(V + E) et indique qu’un cycle existe, mais ne permet pas facilement de déterminer quelle arête précise est redondante. DSU est préférable pour les problèmes qui vous demandent d’identifier l’arête redondante précise, car vous la trouvez naturellement lorsque union échoue.
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # FalseDétection des cycles dans les graphes orientés
Pour les graphes orientés, la détection des cycles avec DSU ne fonctionne pas directement, car les arêtes ont une direction. Utilisez plutôt un DFS avec marquage en trois couleurs : blanc (non visité), gris (dans le chemin actuel du DFS), noir (entièrement traité). Une arête de retour vers un nœud gris indique un cycle.
Dans un graphe non orienté, toute arête de retour indique un cycle. Dans un graphe orienté, une arête transversale vers un nœud noir ne constitue pas un cycle — seules les arêtes de retour vers des nœuds gris en constituent un. Cette distinction est essentielle et fait l’objet de vérifications dans les problèmes de planification de cours.
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # FalseConnexion redondante II : variante pour les graphes orientés
LeetCode 685 étend le problème aux graphes orientés dans lesquels chaque nœud possède exactement un parent (formant un arbre enraciné avec une arête supplémentaire). Deux cas sont possibles : soit un nœud possède deux parents (degré entrant égal à 2), soit il existe un cycle sans qu’aucun nœud n’ait deux parents.
La solution recherche d’abord les nœuds de degré entrant égal à 2. Si elle en trouve un, l’une de ses deux arêtes entrantes doit être la réponse. La détection de cycles avec DSU détermine ensuite laquelle des deux arêtes candidates doit être supprimée. Cette approche en deux phases traite correctement tous les cas.
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]Validité du graphe après suppression d’une arête
Après avoir identifié l’arête redondante, nous pouvons vérifier le résultat en contrôlant que sa suppression laisse un arbre valide : exactement n-1 arêtes, tous les nœuds connexes et aucun cycle. Dans le cadre du problème d’entretien, DSU garantit naturellement cette propriété : si nous renvoyons l’arête dont union a échoué, sa suppression nous laisse exactement les n-1 arêtes dont union a réussi, lesquelles forment un arbre couvrant.
C’est cette garantie qui rend DSU si élégant pour ce problème : les unions réussies construisent progressivement l’arbre, tandis que l’union qui échoue identifie l’unique arête qui n’en fait pas partie.
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removalAnalyse de la complexité temporelle et spatiale
La solution de connexion redondante fondée sur DSU traite chacune des n arêtes exactement une fois, et chaque opération union/find coûte O(alpha(n)) en temps amorti. Temps total : O(n × alpha(n)), soit en pratique O(n).
La complexité spatiale est de O(n) pour les tableaux de parents et de rangs. C’est optimal : vous devez au minimum lire les n arêtes et stocker un certain état pour chaque nœud. Comparez cela à une approche naïve qui exécute un DFS après chaque insertion d’arête : O(n²) en temps et O(n + E) en espace.
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')Cas limite : boucle sur soi-même
Une arête formant une boucle sur soi-même [u, u] crée immédiatement un cycle, puisque ses deux extrémités sont le même nœud. Dans DSU, find(u) == find(u) est toujours vrai : union échoue donc immédiatement et [u, u] est renvoyée comme arête redondante.
La plupart des contraintes des problèmes garantissent l’absence de boucles sur soi-même, mais un code robuste doit les gérer. L’implémentation de DSU les traite naturellement sans cas particulier : la vérification de cycle if find(u) == find(v) les détecte avant toute tentative de union. Vérifiez toujours le comportement avec des entrées couvrant les cas limites, comme les boucles sur un seul nœud et les entrées de taille minimale.
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]Généraliser la détection des cycles entre les algorithmes
Plusieurs algorithmes détectent les cycles, chacun étant adapté à des situations différentes :
- DSU : graphes non orientés, arrivée des arêtes en ligne, O(alpha(n)) par arête — idéal pour compter les cycles ou trouver l’arête redondante
- DFS avec suivi du parent : graphes non orientés, toutes les arêtes connues à l’avance, O(V+E) — idéal lorsque vous avez besoin du chemin du cycle
- DFS à trois couleurs : graphes orientés, détection des arêtes de retour, O(V+E) — idéal pour la planification de cours et le tri topologique
- Tri topologique (de Kahn) : graphes orientés, détection d’un cycle grâce aux nœuds restants de degré entrant non nul — idéal lorsque vous avez également besoin d’un ordre
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')Solution complète avec gestion des cas limites
Voici une solution de qualité production au problème de la connexion redondante, qui gère tous les cas limites : nœuds indexés à partir de 1, exactement une arête redondante et garantie que sa suppression laisse un arbre valide. Elle utilise le DSU optimal avec réduction de moitié des chemins et union par rang.
Après l’envoi de votre solution, essayez la question complémentaire : que se passerait-il si le graphe pouvait contenir plusieurs arêtes redondantes ? Vous devriez suivre toutes les arêtes qui complètent un cycle et renvoyer la dernière dans l’entrée — la même stratégie gloutonne fonctionne toujours, car DSU traite les arêtes dans l’ordre.
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris qu’une connexion redondante est une arête qui relie deux nœuds déjà connectés dans un graphe non orienté, que DSU la détecte en vérifiant find(u) == find(v) avant union, puis en renvoyant cette arête, et que les graphes orientés nécessitent un DFS à trois couleurs ou l’algorithme de Kahn au lieu de DSU pour la détection des cycles. Ensuite, nous appliquerons DSU au problème de fusion de comptes, où les e-mails sont les nœuds et où les e-mails communs entre les comptes déclenchent des unions.
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 « Connexion redondante et détection de cycles » est-elle gratuite ?
Oui — le texte complet de « Connexion redondante et détection de cycles » 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Connexion redondante et détection de cycles » ?
Détectez l’arête qui crée un cycle dans un graphe non orienté en appliquant union à chaque arête et en vérifiant si deux nœuds sont déjà connectés. Tu pratiques DSA 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 DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA 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 « Connexion redondante et détection de cycles » ?
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 DSA Interview Prep ?
Oui. Chaque leçon DSA 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
- DSU avec compression de chemin
- Union par rang et borne de l’inverse d’Ackermann
- Connexion redondante et détection de cycles
- Fusion de comptes et composantes connexes