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

How to Build Free WordPress Contact Us Form with JetFormBuilder? (Step-by-step)

publish the wp form to the page

Systems Engineering in the Ski Industry

Pricing options of an App Service

Week 14: Hoopsnake + Recursive Definitions

Lab 8: Output: Servo motors

UBA’S Monthly Report

Seaborn Data Visualisation: A Complete Overview

Introduction to COCOS2D Game Development and evolution to COCOS creator 3.0

COCOS2D Game Development Companies in Bangalore India

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

Applying Machine Learning for A/B Hypothesis testing: SmartAd performance

Product Portfolio 2020 — Milk Zero (Concept testing)

Analysis of 53 Part Speedrun: Part 15: The Second Problem with Types

Analyzing Features Extracted from IEEG Data for Seizure Detection