중복 간선과 사이클 탐지
각 간선에 합치기를 적용하고 두 노드가 이미 연결되어 있는지 확인해 무방향 그래프에서 사이클을 만드는 간선을 탐지합니다.
중복 간선과 사이클 탐지은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
중복 연결이란 무엇입니까?
중복 연결 문제(LeetCode 684)에서는 n개 노드로 이루어진 트리와 사이클을 정확히 하나 형성하는 추가 간선 하나가 주어집니다. 간선을 제거했을 때 트리가 복원되도록 하는 간선을 찾는 것이 과제입니다. 답이 여러 개라면 입력 목록에서 마지막 간선을 반환합니다.
n개 노드로 이루어진 트리는 간선이 정확히 n-1개이고 연결되어 있으며 사이클이 없습니다. 여기에 간선 하나를 추가하면 사이클이 정확히 하나 생깁니다. 추가된 중복 간선은 이미 같은 컴포넌트에 속해 있던 두 노드를 연결하므로, 이는 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)인지 확인합니다. 두 노드가 같은 루트를 공유한다면 이미 연결된 것이므로, 이 간선을 추가하면 사이클이 생깁니다. 이것이 중복 간선입니다.
이 방법은 무방향 그래프에서 작동합니다. 각 간선에 대해 두 컴포넌트를 성공적으로 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)=루트, find(3)=3, 서로 다름 — union을 수행합니다. 컴포넌트: {1,2,3}
- 간선 [2,3]: find(2)=루트, find(3)=루트 — 같은 루트입니다! 사이클을 탐지했습니다. [2,3]을 반환합니다.
알고리즘은 간선을 순서대로 처리하고 사이클을 처음 완성하는 간선을 반환합니다. 문제에서 추가 간선이 하나뿐이라고 보장하므로, 이것이 항상 올바른 중복 간선입니다.
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를 사용한 사이클 탐지가 직접 작동하지 않습니다. 대신 세 가지 색 표시를 사용하는 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]])) # False중복 연결 II: 방향 그래프 변형
LeetCode 685는 각 노드가 정확히 하나의 부모를 가지는 방향 그래프 문제로 확장한 것입니다. 이 그래프는 추가 간선 하나가 있는 루트 트리를 이룹니다. 두 가지 경우가 발생합니다. 한 노드에 부모가 두 개 있는 경우(진입 차수 2) 또는 어떤 노드에도 부모가 두 개는 없지만 사이클이 있는 경우입니다.
해법은 먼저 진입 차수가 2인 노드를 확인합니다. 그런 노드가 발견되면 두 개의 들어오는 간선 중 하나가 답이 됩니다. 그런 다음 DSU 사이클 탐지로 두 후보 간선 중 어느 것을 제거해야 하는지 결정합니다. 이 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은 트리에 속하지 않는 간선을 식별합니다.
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개의 간선을 각각 정확히 한 번 처리하며, 각 union/find 연산의 비용은 상각 O(alpha(n))입니다. 전체 시간은 O(n × alpha(n))으로, 사실상 O(n)입니다.
공간 복잡도는 부모 배열과 랭크 배열에 필요한 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을 시도하기 전에 이를 포착하기 때문입니다. 단일 노드 루프와 최소 크기 입력 같은 경계 사례 입력으로 항상 verify하십시오.
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) — 사이클 경로가 필요할 때 가장 적합
- 세 가지 색 DFS: 방향 그래프, 역간선 탐지, O(V+E) — 수강 일정 및 위상 정렬에 가장 적합
- 위상 정렬(Kahn 방식): 방향 그래프, 남은 진입 차수가 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부터 시작하는 노드 인덱스, 정확히 하나의 중복 간선, 그리고 해당 간선을 제거하면 유효한 트리가 된다는 보장을 비롯한 모든 경계 사례를 처리하는 실전 수준의 중복 연결 풀이가 있습니다. 이 풀이는 경로 절반 압축과 랭크에 의한 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))빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 확인해 보십시오.
단원 요약
이 단원에서는 중복 연결은 무방향 그래프에서 이미 연결된 두 노드를 연결하는 간선이라는 것, DSU는 union 전에 find(u) == find(v)를 확인하고 해당 간선을 반환하여 이를 탐지한다는 것, 그리고 방향 그래프의 사이클 탐지에는 DSU 대신 세 가지 색 DFS 또는 Kahn 알고리즘이 필요하다는 것을 배웠습니다. 다음으로는 이메일이 노드가 되고 계정 간 공유 이메일이 union을 발생시키는 계정 병합 문제에 DSU를 적용해 보겠습니다.
자주 묻는 질문
“중복 간선과 사이클 탐지” 강의는 무료인가요?
네 — “중복 간선과 사이클 탐지” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“중복 간선과 사이클 탐지”에서 뭘 배우나요?
각 간선에 합치기를 적용하고 두 노드가 이미 연결되어 있는지 확인해 무방향 그래프에서 사이클을 만드는 간선을 탐지합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“중복 간선과 사이클 탐지” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 경로 압축을 적용한 DSU
- 랭크에 의한 합치기와 역 아커만 상한
- 중복 간선과 사이클 탐지
- 계정 병합과 연결 요소