Critical Connections in a Network

Problem Id: 1192 Difficulty: Hard Tag: Depth-first Search


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):
        self.adj[p].append(q)
        self.adj[q].append(p)


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

        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