Hard graph problem: find bridges in a graph
If you want to find a cycle in a graph, we have a standard algorithm named
However, if we encounter a similar problem, some simple version code can be used to solve the problem.
Recall graph representation and complexities
Time complexity of BFS/DFS O(V+E) and O(V²) if the graph is stored as Adjacency List and Adjacency Matrix, respectively.
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’.
Similarly, a ‘Bridge’ is defined as an edge in a graph G whose removal disconnects G. These two problems are usually defined for undirected graphs (they are more challenging for directed graphs and require another algorithm to solve.)
A naive algorithm to find articulation points is as follows:
Run O(V+E) DFS to count number of connected components of the original graph. Usually, the input is a connected graph, so this check will usually gives us one connected component.
For each vertex v in V // O(V):
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)).
The DFS variant, due to John Edward Hopcroft and Robert Endre Tarjan, can be briefly described here:
Maintain two numbers: dfs_num(u) and dfs_low(u). dfs_num(u) stores the iretation counter when the vertes u is visited for the first time (not just for distinguishing UNVISITED verseus EXPLORED/VISITED). The other number dfs_low(u) stores the lowest dfs_num reachable from the current DFS spanning subtree of u. At the beginning, dfs_low(u) = dfs_num(u) when vertex u is visited for the first time. The, dfs_low(u) can only be made smaller if there is a cycle. Note that we do not update dfs_low(u) with a back edge (u,v) if v is a direct parent of u.
If you want to know more detail about this algorithm, please visit this link
https://codeforces.com/blog/entry/71146
Leetcode Problem
1192. Critical Connections in a Network
Naive TLE solution
A naive solution will get TLE:
- block each connect to see whether all nodes still can be connected after block.
- If can, then it is not a critical connection. If not, it is.
For checking the connection, we can use union find. The complexity of Union find is O(E) and as we are going to check E edges, so the complexity is O(E²). As we can have up to 10⁵ nodes, it is not surprising that we get TLE.
8 / 12 test cases passed.
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.
Here is a simple code modified from this link
The runtime of below code:
Runtime: 2412 ms, faster than 58.30% of Python3 online submissions for Critical Connections in a Network.
Memory Usage: 84.1 MB, less than 100.00% of Python3 online submissions for Critical Connections in a Network.
Time complexity:
O(V+E)
Space complexity: O(graph) + O(rank) + O(connections) = O(E)+O(E)+O(E) =O(E)
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 resVery 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 resWhen the test case is below, we have the output:
test case
6
[[0,1],[1,2],[1,3],[1,4],[4,5],[1,5]]
output
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 1, 1]
The output of this one. is not exactly the same on the same test case. Here is the output of this one.
[0, 1, 2, 2, 2, 3]
[0, 1, 2, 2, 1, 1]
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 resA question about the condition checking
Why we can not use
if dfs_low[u]!=dfs_low[v]:
instead of
if dfs_low[u] > dfs_num[v] or dfs_low[v] > dfs_num[u]:
Based on Tarjan Algorithm, we should check dfs_low[u] > dfs_num[v] or dfs_low[v] > dfs_num[u] to decide whether it is a bridge.
If we do that, it is almost correct except some special cases. For this leetcode question, we have
11 / 12 test cases passed. And the last one can not pass.
Still cannot find a very intuitive way to generate a counter example. If the reader knows any, please leave a comment. Thanks a lot.
