0%

Tarjan's algorithm

Find Strong Connected Components (SCC)

Video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def find_scc(n: int, edges: List[List[int]]):
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

ids, low = [-1] * n, [-1] * n
stack, in_stack = [], [False] * n
id_max = 0

def dfs(u):
nonlocal id_max
stack.append(u)
in_stack[u] = True
ids[u] = low[u] = id_max
id_max += 1

for v in graph[u]:
if ids[v] == -1: dfs(v)
if in_stack[v]:
low[u] = min(low[u], low[v])

if low[u] == ids[u]:
while True:
node = stack.pop()
in_stack[node] = False
if node == u: break

for i in range(n):
if ids[i] == -1:
dfs(i)
return low

Find Cutting Edge

Video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def criticalConnections(n: int, edges: List[List[int]]) -> List[List[int]]:
graph = [[] for i in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)

ids, low = [-1] * n, [0] * n
id_max, bridges = 0, []

def dfs(u, parent):
nonlocal id_max
ids[u] = low[u] = id_max
id_max += 1

for v in graph[u]:
if v == parent: continue
if ids[v] == -1:
dfs(v, u)
low[u] = min(low[u], low[v])
if ids[u] < low[v]:
bridges.append((u, v))
else:
low[u] = min(low[u], ids[v])
for i in range(n):
if ids[i] != -1: continue
dfs(i, -1)
return bridges

edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (2, 5), (5, 6), (6, 7), (7, 8), (8, 5)]
assert sorted([(3, 4), (2, 3), (2, 5)]) == sorted(criticalConnections(9, edges))

Find Cut Vertices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def cut_vertex(n: int, edges: List[List[int]]):
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

ids, low = [-1] * n, [-1] * n
is_cut, id_max = [False] * n, 0

def dfs(u, p, root):
nonlocal out_edge
nonlocal id_max
if p == root:
out_edge += 1
ids[u] = low[u] = id_max
id_max += 1

for v in graph[u]:
if v == p: continue
if ids[v] == -1:
dfs(v, u, root)
low[u] = min(low[u], low[v])
if low[v] >= ids[u]:
is_cut[u] = True
else:
low[u] = min(low[u], ids[v])

for i in range(n):
if ids[i] == -1:
out_edge = 0
dfs(i, -1, i)
is_cut[i] = out_edge > 1

return is_cut

edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (2, 5), (5, 6), (6, 7), (7, 8), (8, 5)]
assert [False, False, True, True, False, True, False, False, False] == cut_vertex(9, edges)