 # Articulation points tarjan algorithm

Jun 26th, 2022 (edited)
770
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
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
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]
39.
40. #alternatively we can remove vis array and use disc array as vis array combiningly
41.
42. import sys
43. sys.setrecursionlimit(10**6)
44.
45. class Solution:
46.
47.     #Function to return Breadth First Traversal of given graph.
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
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