Open seungriyou opened 8 months ago
https://leetcode.com/problems/redundant-connection/
undirected graph의 cycle detection 문제이다.
cycle을 형성하는 edge 중 가장 마지막으로 등장하는 edge를 반환해야하므로, 그래프를 동시에 구성해나가야 한다.
또한, edge와 node의 개수가 같으므로 cycle을 형성하는 edge는 단 하나일 것이다.
[!important] 그래프의 cycle detection에 대해 정리한 포스팅: https://seungriyou.github.io/posts/undirected-and-directed-graph-cycle-detection/ [LC] 207. Course Schedule(#42)은 directed graph의 cycle detection 문제였다.
[!important] 그래프의 cycle detection에 대해 정리한 포스팅: https://seungriyou.github.io/posts/undirected-and-directed-graph-cycle-detection/
[LC] 207. Course Schedule(#42)은 directed graph의 cycle detection 문제였다.
주어진 edges를 순회하면서 두 node에 대해 다음의 연산을 수행한다.
edges
find
union
주어진 edges를 순회하면서 DFS를 수행(dfs(a, b))하고, 동시에 그래프를 구성해나간다.
dfs(a, b)
두 node에 대해 한 쪽 node의 인접 node를 차례로 타고 DFS를 수행(dfs(a_neighbor, b))하다가, 두 node가 같아지면 cycle이 감지된 것이다.
dfs(a_neighbor, b)
n= # of vertices, m= # of edges
n
m
O(n * α(n))
O(n^2)
O(n)
Approach
undirected graph의 cycle detection 문제이다.
cycle을 형성하는 edge 중 가장 마지막으로 등장하는 edge를 반환해야하므로, 그래프를 동시에 구성해나가야 한다.
또한, edge와 node의 개수가 같으므로 cycle을 형성하는 edge는 단 하나일 것이다.
Idea 1: Union-Find
주어진
edges를 순회하면서 두 node에 대해 다음의 연산을 수행한다.find결과가 같은 경우: cycle이 감지되었으므로, 해당 edge를 반환한다. (edge와 node의 개수가 같으므로, 해당 edge가 마지막으로 등장하는 edge가 된다.)find결과가 같지 않은 경우:union하여 그래프를 구성해나간다.Idea 2: DFS
주어진
edges를 순회하면서 DFS를 수행(dfs(a, b))하고, 동시에 그래프를 구성해나간다.두 node에 대해 한 쪽 node의 인접 node를 차례로 타고 DFS를 수행(
dfs(a_neighbor, b))하다가, 두 node가 같아지면 cycle이 감지된 것이다.Complexity
O(n * α(n))(path compression) (ref)O(n^2)(최악의 경우, 각 노드 & 간선 모두 한 번씩 방문 -> 동시에 그래프 구성) (ref1, ref2)O(n)(parent list)O(n)(graph & recursive stack)