 # Find bridge in graph

Jun 26th, 2022
754
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. when disc[u]<low[v]-------------------------->(1)
3. add (u,v) to bridge list
4. In case of articulation point we use condition disc[u]<=low[v] and root children condition.
5. Here we use only one condition and remember there is no equal condition in (1) which differs from articulation points
6. '''
7. from collections import defaultdict as dd
8. class Solution:
9.     def criticalConnections(self, n: int, cons: List[List[int]]) -> List[List[int]]:
11.         for u,v in cons:
14.         parent,disc,low,time,ans=[-1]*n,[-1]*n,*n,0,[]
15.         def dfs(u):
16.             nonlocal time
17.             low[u]=disc[u]=time
18.             time+=1
20.                 if v==parent[u]:continue#ignore parent
21.                 if disc[v]==-1:#if not visited
22.                     parent[v]=u
23.                     dfs(v)
24.                     low[u]=min(low[u],low[v])
25.                     if disc[u]<low[v]:#----------------------->VVIMP condition
26.                         ans.append((u,v))
27.                 else:
28.                     low[u]=min(low[u],disc[v])#--------------->for visited nodes same as tarjan algo+articulation points
29.         for i in range(n):
30.             if disc[i]==-1:
31.                 dfs(i)
32.         return ans