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`

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

--

--

--

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Jimmy Shen

Data Scientist/MLE/SWE @takemobi