Advertisement
Iam_Sandeep

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]]:
  10.         adj=dd(set)
  11.         for u,v in cons:
  12.             adj[u].add(v)
  13.             adj[v].add(u)
  14.         parent,disc,low,time,ans=[-1]*n,[-1]*n,[0]*n,0,[]
  15.         def dfs(u):
  16.             nonlocal time
  17.             low[u]=disc[u]=time
  18.             time+=1
  19.             for v in adj[u]:
  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
Advertisement
RAW Paste Data Copied
Advertisement