# Critical Connections in a Network   ## Intuition

This problem is about cycle detect. If an edge is in a cycle, then it is not a critical connection.

In undirected graph, a simple cycle should always be a path in spanning tree plus one additional path which linked the node and one of its ancestor. BTW, if node a and node b are in the same simple cycle, b and c are in another simple cycle, then a and c must be in a cycle (maybe not a simple cycle).

So we could use DSU, once we detected a cycle, we union all vertices in this cycle together. And finally, if an edge links 2 different connected components, it must be critical.

## Solution

``````
class DSU:
def __init__(self, size):
self.size = size
self.root = list(range(size))

def find(self, p):
if self.root[p] != p:
self.root[p] = self.find(self.root[p])
return self.root[p]

def union(self, p, q):
rp, rq = self.find(p), self.find(q)
if rp != rq:
self.root[rp] = rq

def connected(self, p, q):
return self.find(p) == self.find(q)

class Graph:
def __init__(self, size):
self.size = size
self.adj = [[] for _ in range(size)]

def add_edge(self, p, q):

class Solution:
def criticalConnections(self, n, connections):
graph = Graph(n)
for p, q in connections:

self.visited = [False] * n
self.on_stack = [False] * n
self.parent = [None] * n
self.dsu = DSU(n)

self.dfs(graph, 0)

critical = []
for p, q in connections:
if not self.dsu.connected(p, q):
critical.append([p, q])
return critical

def dfs(self, graph, vertex):
self.visited[vertex] = True
self.on_stack[vertex] = True
for child in graph.adj[vertex]:
if not self.visited[child]:
self.parent[child] = vertex
self.dfs(graph, child)
elif child != self.parent[vertex] and self.on_stack[child]:
# Detect a cycle. All nodes are in the path in the spanning
# tree from child (actually vertex's ancestor) to this vertex.
tmp = vertex
while not self.dsu.connected(tmp, child):
self.dsu.union(child, tmp)
tmp = self.parent[tmp]
self.on_stack[vertex] = False
``````