# 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 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

When 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 res

# A 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.