0%

Detect Cycle in a Graph

Undirected Graph

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def hasCycle(n: int, edges: List[List]) -> bool:
def dfs(u, parent):
visited.add(u)
for v in graph[u]:
if v == parent: continue
if v in visited or dfs(v, u):
return True
return False

graph, visited = defaultdict(set), set()
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False

Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def hasCycle(n: int, edges: List[List]) -> bool:
uf = {}
def find(x):
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(x, y): # x -> y
uf[find(x)] = find(y)

for u, v in edges:
if find(u) == find(v):
return True
union(u, v)
return False

Practice

Directed Graph

DFS + Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def hasCycle(n: int, edges: List[List]) -> bool:
def dfs(u):
stack.add(u), visited.add(u)
for v in graph[u]:
if v not in visited:
if dfs(v):
return True
elif v in stack:
return True
stack.remove(u)
return False

graph, visited, stack = defaultdict(set), set(), set()
for u, v in edges:
graph[u].add(v)

for u in range(n):
if u not in visited and dfs(u):
return True
return False

Practice

  1. 207. Course Schedule