Articulation points tarjan algorithm

Jun 26th, 2022 (edited)
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.87 KB | None
  1. '''
  2. The idea is to use DFS (Depth First Search). In DFS, we follow vertices in tree form called DFS tree. In DFS tree, a vertex u is parent of another vertex v, if v is discovered by u (obviously v is an adjacent of u in graph).
  3. In DFS tree, a vertex u is articulation point if one of the following two conditions is true.
  4. 1.u is root of DFS tree and it has at least two children.
  5. 2.u is not root of DFS tree and it has a child v such that no vertex in subtree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.
  6. '''
  7. class Solution:
  8.     #Function to return Breadth First Traversal of given graph.
  9.     def articulationPoints(self, n, adj):
  10.         #ap:articulation point
  11.         parent,disc,low,time,ap,vis=[-1]*n,[1e9]*n,[1e9]*n,0,[False]*n,[False]*n
  12.         def dfs(u):
  13.             nonlocal time
  14.             vis[u]=True
  15.             disc[u]=low[u]=time
  16.             time+=1
  17.             children=0
  18.             for v in adj[u]:
  19.                 if vis[v]==False:
  20.                     children+=1
  21.                     parent[v]=u
  22.                     dfs(v)
  23.                     low[u]=min(low[v],low[u])
  24.                     #condition for root of dfs tree
  25.                     if parent[u]==-1 and children>=2:
  26.                         ap[u]=True
  27.                     #condition for non root disc[u]<=low[v]----->VVIMP
  28.                     elif parent[u]!=-1 and disc[u]<=low[v]:
  29.                         ap[u]=True
  30.                 #already vertices which are not main parent. We need to update low time there
  31.                 #low[u]=min(disc[v],low[u]) -------->vvvimp
  32.                 elif v!=parent[u]:
  33.                     low[u]=min(disc[v],low[u])
  34.         for i in range(n):
  35.             if vis[i]==False:
  36.                 dfs(i)
  37.         t=[i for i,j in enumerate(ap) if j==True]
  38.         return t if t else [-1]
  40. #alternatively we can remove vis array and use disc array as vis array combiningly
  42. import sys
  43. sys.setrecursionlimit(10**6)
  45. class Solution:
  47.     #Function to return Breadth First Traversal of given graph.
  48.     def articulationPoints(self, n, adj):
  49.         parent,disc,low,time,ap=[-1]*n,[-1]*n,[1e9]*n,0,[False]*n
  50.         def dfs(u):
  51.             nonlocal time
  52.             disc[u]=low[u]=time
  53.             time+=1
  54.             children=0
  55.             for v in adj[u]:
  56.                 if disc[v]==-1:
  57.                     children+=1
  58.                     parent[v]=u
  59.                     dfs(v)
  60.                     low[u]=min(low[v],low[u])
  61.                     if parent[u]==-1 and children>=2:
  62.                         ap[u]=True
  63.                     elif parent[u]!=-1 and disc[u]<=low[v]:
  64.                         ap[u]=True
  65.                 elif v!=parent[u]:
  66.                     low[u]=min(disc[v],low[u])
  67.         for i in range(n):
  68.             if disc[i]==-1:
  69.                 dfs(i)
  70.         t=[i for i,j in enumerate(ap) if j==True]
  71.         return t if t else [-1]
RAW Paste Data Copied