Hard graph problem: find bridges in a graph

Recall graph representation and complexities

Reference: competitive programming

Articulation Points and Bridges

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.

Leetcode Problem

Naive TLE solution

  1. block each connect to see whether all nodes still can be connected after block.
  2. 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

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

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

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Getting Started with ServiceNow Dynamic Translations

Rails 6 adds rails db:prepare to create and migrate and seed the database

Write Better SQL — Use Window Functions

Lesson for git checkout remote

Image to Patches in pytorch

Senior Software Engineer

Python In 7 Days - 01/7: The History of Python and Its Features.

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

More from Medium

BANKING CUSTOMERs Prediction Using Machine Learning

Overcome Imbalance in your datasets — PART II

Watch: Phil Taylor explains how NERD uses entity recognition to unlock the full potential of…

Transfer Learning: Summarizing Medical Documents