LC 1192 [H] Critical Connections in a Network - ALawliet/algorithms GitHub Wiki

"find the bridges in the graph"

a bridge is an edge in an undirected graph which when removed disconnects the graph

where an unvisited nodes has low[v] > dis[u], which means that v has no connectivity to earlier nodes than u

use DFS
while we visit each node assign discovery time disc and value low
disc - the time when node is visited
low - whether there's some other early node (based on that disk) that can be visited by the subtree rooted with that node (the lowest low when visited or the lowest disk)

need to compare the low values of both nodes to update the information of connectivity to the lowest node possible

not visited:
  low[u] = min(low[u], low[v])
  low[v] > dis[u]: is critical connection
visited:
  low[u] = min(low[u], disc[v])

https://www.youtube.com/watch?v=thLQYBlz2DM&ab_channel=GeeksforGeeks

https://www.youtube.com/watch?v=erlX-1MJlv8&ab_channel=CrisaG

if dis[u] < low[v] this means that v is not connected to any earlier node than u

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        dis = [0]*n
        low = [0]*n
        self.time = 0
        visited = set()
        critical_connections = []
        G = defaultdict(list)
        
        for u, v in connections:
            G[u].append(v) ; G[v].append(u)
            
        def dfs(u, parent):
            visited.add(u)

            self.time += 1
            dis[u] = low[u] = self.time
            
            for v in G[u]:
                if v == parent: continue

                if v not in visited: # it can't be a backedge
                    dfs(v, u)

                    low[u] = min(low[u], low[v]) # update low with low
                
                    # bridge at start of cycle (cause it's not in visited), not a backedge
                    if low[v] > dis[u]: # check low to dis
                        critical_connections.append( [u, v] )
                else:
                    # if neighbor has been visited, and it is not parent, it is backedge
                    # if visited check it is backedge
                    # if it is is a backedge, we have a way to get back, graph not disconnected
                    # if v != parent:
                    low[u] = min(low[u], dis[v]) # update low to dis
                    
        dfs(0, None)
        
        return critical_connections

class Solution:
    def criticalConnections2(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        def dfs(u, parent, preLabel):
            # already visited
            if labels[u] >= 0:
                return labels[u]
            
            # assign label for current node
            labels[u] = preLabel + 1
            minLabel = sys.maxsize
            
            for v in G[u]:
                # if neighbor is a parent, don't revisit it 
                if v == parent:
                    continue
                    
                recursiveLabel = dfs(v, u, labels[u])
                
                # u and v are both part of a circle, so not critical connection
                if labels[u] >= recursiveLabel:
                    critical_connections.remove( (min(u,v), max(u,v)) )
                    
                minLabel = min(minLabel, recursiveLabel)
                
            return minLabel

        G = defaultdict(list)
        critical_connections = set()

        for u, v in connections:
            G[u].append(v) ; G[v].append(u)
            critical_connections.add( (min(u,v), max(u,v)) )

        labels = [-1] * n # tarjan's discovery

        dfs(0, None, 0)

        return critical_connections