Redundant Connectionと閉路検出
各辺に対してunionを適用し、2つの頂点がすでに連結されているか確認することで、無向グラフに閉路を作る辺を検出します。
「Redundant Connectionと閉路検出」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
冗長な接続とは
Redundant Connection 問題（LeetCode 684）では、n 個のノードからなる木と、ちょうど 1 本の余分な辺が与えられます。この余分な辺によって、ちょうど 1 つの閉路が形成されます。辺を 1 本削除して木に戻すとき、その削除すべき辺を見つけてください。複数の答えがある場合は、入力リストの最後に現れる辺を返します。
n 個のノードからなる木には、ちょうど n-1 本の辺があり、連結していて閉路はありません。そこにもう 1 本辺を追加すると、ちょうど 1 つの閉路ができます。追加された（冗長な）辺は、すでに同じ連結成分に属していた 2 つのノードを結びます。これは 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')DSU による閉路検出
DSU は自然に閉路を検出できます。辺 (u, v) を追加する前に、find(u) == find(v) を確認します。同じルートを持つ場合、2 つのノードはすでに連結されているため、この辺を追加すると閉路ができます。これが冗長な辺です。
この方法は無向グラフで機能します。各辺について、2 つの連結成分の union に成功する（まだ閉路はない）か、両端点がすでに同じ連結成分に属していることを検出する（閉路が見つかる）かのどちらかになります。時間計算量は O(n × alpha(n)) で、ほぼ 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]アルゴリズムを順に追跡する
[[1,2],[1,3],[2,3]] を例に、手順を追って確認しましょう。最初は各ノードがそれぞれ独立した連結成分です: {1}, {2}, {3}。
- 辺 [1,2]: find(1)=1、find(2)=2 で異なるため、union します。連結成分: {1,2}, {3}
- 辺 [1,3]: find(1)=root、find(3)=3 で異なるため、union します。連結成分: {1,2,3}
- 辺 [2,3]: find(2)=root、find(3)=root で同じルートです。閉路を検出しました。[2,3] を返します。
アルゴリズムは辺を順番に処理し、閉路を完成させる最初の辺を返します。余分な辺は 1 本だけと保証されているため、これが常に正しい冗長な辺になります。
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)DFS による無向グラフの閉路検出
無向グラフの閉路検出では、DSU の代わりに親を追跡する DFSを使う方法もあります。DFS 中に、すでに訪問済みで、かつ現在のノードの直接の親ではないノードに到達した場合、後退辺が見つかったことになり、閉路を示します。
ただし、DFS の方法は O(V + E) の時間が必要で、閉路が存在するかどうかは返せますが、どの辺が冗長なのかを簡単に特定することはできません。特定の冗長な辺を見つける問題では、union に失敗した時点で自然にその辺を特定できるため、DSU が適しています。
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]])) # False有向グラフの閉路検出
有向グラフでは辺に向きがあるため、DSU による閉路検出をそのまま使うことはできません。代わりに、3 色による DFSを使います。白は未訪問、灰色は現在の DFS パス上、黒は処理完了を表します。灰色のノードへ戻る後退辺がある場合、閉路が存在します。
無向グラフでは、どの後退辺も閉路を意味します。一方、有向グラフでは、黒いノードへの横断辺は閉路ではありません。閉路を示すのは灰色のノードへの後退辺だけです。この違いは重要で、コーススケジュールの問題で問われます。
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]])) # FalseRedundant Connection II: 有向グラフ版
LeetCode 685 では、各ノードがちょうど 1 つの親を持つ有向グラフ（余分な辺が 1 本ある根付き木）へと問題を拡張しています。考えられるケースは 2 つあります。あるノードに 2 つの親がある場合（入次数が 2 の場合）と、どのノードにも 2 つの親がない状態で閉路がある場合です。
解法ではまず、入次数が 2 のノードを確認します。見つかった場合、そのノードへ入る 2 本の辺のどちらか一方が答えです。次に DSU による閉路検出を使い、候補となる 2 本の辺のうち、どちらを削除すべきかを判定します。この 2 段階の方法ですべてのケースを正しく処理できます。
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]辺を削除した後のグラフの妥当性
冗長な辺を特定した後、その辺を削除しても有効な木が残ることを確認できます。つまり、辺がちょうど n-1 本あり、すべてのノードが連結していて、閉路がないことを確認します。面接問題の条件では、DSU によってこれが自然に保証されます。union に失敗した辺を返すと、それを削除した後に残るのは、union に成功したちょうど n-1 本の辺であり、それらが全域木を形成するためです。
この保証があるため、この問題では DSU をすっきり使えます。成功した union が木を段階的に構築し、失敗した union によって木に属さない 1 本の辺を特定できるのです。
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 removal時間計算量と空間計算量の分析
DSU を使った冗長な接続の解法では、n 本の辺をそれぞれ 1 回だけ処理し、各 union/find 操作の償却計算量は O(alpha(n)) です。全体の時間計算量は O(n × alpha(n)) で、実質的に O(n) です。
空間計算量は、parent 配列と rank 配列のための O(n) です。これは最適です。少なくとも n 本の辺をすべて読み込み、各ノードについて何らかの状態を保持する必要があるためです。各辺の追加後に DFS を実行する単純な方法と比較すると、そちらは時間計算量が O(n²)、空間計算量が O(n + E) になります。
# 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).')エッジケース: 自己ループ
自己ループの辺 [u, u] は、両端点が同じノードであるため、直ちに閉路を作ります。DSU では find(u) == find(u) が常に真になるため、union はすぐに失敗し、[u, u] が冗長な辺として返されます。
ほとんどの問題では自己ループがないと制約で保証されていますが、堅牢なコードではこれにも対応するべきです。DSU の実装なら特別な場合分けをしなくても自然に処理できます。閉路判定の if find(u) == find(v) が、union を試みる前に自己ループを検出するためです。1 ノードのループや最小サイズの入力など、エッジケースの入力でも必ず確認してください。
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]アルゴリズムごとの閉路検出の一般化
閉路を検出するアルゴリズムはいくつもあり、それぞれ適した状況が異なります。
- DSU: 無向グラフ、辺がオンラインで到着、辺ごとに O(alpha(n)) — 個数のカウントや冗長な辺の検出に最適
- 親を追跡する DFS: 無向グラフ、すべての辺が最初から判明、O(V+E) — 閉路の経路が必要な場合に最適
- 3 色による DFS: 有向グラフ、後退辺の検出、O(V+E) — コーススケジュールやトポロジカルソートに最適
- トポロジカルソート（Kahn's）: 有向グラフ、残った入次数が 0 でないノードによって閉路を検出 — 順序も必要な場合に最適
# 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')エッジケースに対応した完全な解法
ここでは、1 始まりのノード番号、冗長な辺がちょうど 1 本であること、そしてその辺を削除すると有効な木が残るという保証など、すべてのエッジケースに対応した Redundant Connection の実用的な解法を示します。パスの半圧縮とランクによる union を使った最適な DSU を採用しています。
提出した後は、次の発展問題にも挑戦してみてください。グラフに複数の冗長な辺が存在する場合はどうなるでしょうか。その場合は、閉路を完成させるすべての辺を記録し、入力の最後に現れる辺を返す必要があります。DSU は辺を順番に処理するため、同じ貪欲戦略がそのまま機能します。
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))理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、冗長な接続とは、無向グラフですでに連結している 2 つのノードを結ぶ辺であること、DSU は union の前に find(u) == find(v) を確認し、その辺を返すことで冗長な接続を検出すること、そして有向グラフの閉路検出には DSU ではなく、3 色による DFS または Kahn's algorithm が必要であることを学びました。次は DSU を accounts-merge 問題に適用します。この問題ではメールアドレスがノードとなり、アカウント間で共有されるメールアドレスが union を発生させます。
よくある質問
「Redundant Connectionと閉路検出」レッスンは無料ですか？
はい。「Redundant Connectionと閉路検出」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Redundant Connectionと閉路検出」で何を学びますか？
各辺に対してunionを適用し、2つの頂点がすでに連結されているか確認することで、無向グラフに閉路を作る辺を検出します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Redundant Connectionと閉路検出」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 経路圧縮付きDSU
- ランクによるUnionと逆アッカーマン境界
- Redundant Connectionと閉路検出
- Accounts Mergeと連結成分