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

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)).

# Leetcode Problem

1192. Critical Connections in a Network

## Naive TLE solution

A naive solution will get TLE:

1. 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

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.

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