Hard graph problem: find bridges in a graph

Recall graph representation and complexities

Reference: competitive programming

Articulation Points and Bridges

Given an undirected graph, an ‘Articulation Point’ is defined as a vertex in a graph G whose removal (all edges incident to this vertex are also removed) disconnects G. A graph without any articulation point is called ‘Biconnected’.

a) Cut vertex v and its incident edges.

b) Run O(V+E) DFS(or BFS) and see if the number of CCs increases.

c) If yes, v is an articulation point. Restore v and its incident edges.

This naive algorithm calls DFS O(V) times, thus it runs in O(V*(V+E)).

Leetcode Problem

1192. Critical Connections in a Network

Naive TLE solution

A naive solution will get TLE:

  1. If can, then it is not a critical connection. If not, it is.
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
def critical(k):
uf = {}
def find(x):
uf.setdefault(x,x)
if uf[x]!=x:
uf[x]=find(uf[x])
return uf[x]
def union(x,y):
uf[find(y)]=find(x)
for i, (u,v) in enumerate(connections):
if i!=k:union(u,v)
return len({find(i) for i in range(n)})!=1
return [connection for k,connection in enumerate(connections) if critical(k)]

Tarjan similar solution

The critical part of this problem is if the edge is part of the cycle, then it is not critical as if we delete this one, the nodes still can be connected by the rest part of the cycle.

class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
graph = collections.defaultdict(list)
for u, v in connections:
graph[u].append(v)
graph[v].append(u)
connections = {tuple(sorted(connection)) for connection in connections}
ranks = [-2]*n

def dfs(node, depth):
if ranks[node] >=0:return ranks[node]
ranks[node] = depth
min_back_depth = n
for neighbor in graph[node]:
if ranks[neighbor] == depth-1:continue
back_depth = dfs(neighbor, depth+1)
if back_depth <= depth:
connections.discard(tuple(sorted([node, neighbor])))
min_back_depth = min(min_back_depth, back_depth)
return min_back_depth

dfs(0, 0)
return list(connections)

Pure Tarjan Algorithm

Slightly modified from this one.

class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
graph = collections.defaultdict(list)
for u, v in connections:
graph[u].append(v)
graph[v].append(u)

dfs_num, dfs_low = [None]*n, [None]*n

def dfs(node, parent, num):
# already visited
if dfs_num[node] is not None:return

dfs_num[node] = dfs_low[node] = num
for neighbor in graph[node]:
if dfs_num[neighbor] is None:
dfs(neighbor, node, num + 1)

# minimal num in the neignbors, exclude the parent
dfs_low[node] = min([num] + [dfs_low[neighbor] for neighbor in graph[node] if neighbor != parent])

dfs(0, None, 0)

res = []
for u, v in connections:
if dfs_low[u] > dfs_num[v] or dfs_low[v] > dfs_num[u]:
res.append([u, v])
return res

Very standard Tarjan algorithm 1

class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
self.num = 0
graph = collections.defaultdict(list)
for key in graph:graph[key].sort()
for u, v in connections:
graph[u].append(v)
graph[v].append(u)

dfs_num, dfs_low = [None]*n, [None]*n

def dfs(node, parent):
# already visited
if dfs_num[node] is not None:return
dfs_num[node] = dfs_low[node] = self.num
self.num += 1
for neighbor in graph[node]:
if dfs_num[neighbor] is None:
dfs(neighbor, node)

# minimal num in the neignbors, exclude the parent
dfs_low[node] = min([dfs_low[node]] + [dfs_low[neighbor] for neighbor in graph[node] if neighbor != parent])

dfs(0, None)

res = []
#print(dfs_num)
#print(dfs_low)
for u, v in connections:
# non bridge
if dfs_low[u] > dfs_num[v] or dfs_low[v] > dfs_num[u]:
res.append([u, v])
return res
Test case: reference competitive programming

Very standard Tarjan algorithm 2

class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
self.num = 0
dfs_num, dfs_low = [None]*n, [None]*n
dfs_parents = [None]*n
graph = collections.defaultdict(list)
for u,v in connections:
graph[u].append(v)
graph[v].append(u)
res = []
def dfs(u):
dfs_num[u] = dfs_low[u] = self.num
self.num += 1
for v in graph[u]:
if dfs_num[v] is None:
dfs_parents[v] = u
dfs(v)
if dfs_low[v]>dfs_num[u]:res.append([u,v])
dfs_low[u] = min(dfs_low[u], dfs_low[v])
elif v!=dfs_parents[u]:
dfs_low[u] = min(dfs_low[u], dfs_low[v])
for i in range(n):
if dfs_num[i] is None:
dfs(i)
#print(dfs_num)
#print(dfs_low)
return res

A question about the condition checking

Why we can not use

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi