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