fork(3) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define pb emplace_back
  5. #define sz 3005 //In the current scenario, I need only a maximum on 3000 vertices
  6.  
  7. typedef long long int ll;
  8.  
  9. //Created by Shreyans Sheth [bholagabbar]
  10.  
  11. bool visited [sz]; //whether the node has been discoverd in the DFS run or not
  12. int low [sz]; //time of the earliest discovered vertex reachable from the vertex
  13. int disc [sz]; //time at which vertex was explored
  14. int parent [sz]; //stores the parents of each vertex
  15. vector<int> a[sz]; //Adjacency List for graph
  16. int rtime; //Time
  17. vector<int> ap; //Stored the articulation points
  18.  
  19. void DFS(int s)
  20. {
  21. 	visited[s]=1;
  22. 	low[s]=disc[s]=++rtime;
  23. 	int nchild=0;
  24. 	for(auto i:a[s])
  25. 	{
  26. 		if(!visited[i])
  27. 		{
  28. 			nchild++;//INcrement children of the current vertex
  29. 			parent[i]=s;
  30. 			DFS(i);
  31. 			low[s]=min(low[s],low[i]);
  32. 			/* s is an articulation point iff
  33. 			 1. It the the root and has more than 1 child.
  34. 			 2. It is not the root and no vertex in the subtree rooted at one of its
  35. 			    children has a back-link to its ancestor.
  36. 			    A child has a back-link to an ancestor of its parent when its low
  37. 			    value is less than the discovery time of its parent.*/
  38. 				if((parent[s]==-1 && nchild>1)||(parent[s]!=-1 && low[i]>=disc[s]))
  39. 					ap.pb(s);//Adding the articulation points. How are they repeated?
  40. 		}
  41. 		else if(visited[i] && i!=parent[s])
  42. 			low[s]=min(low[s],disc[i]);
  43. 	}
  44.  
  45. }
  46.  
  47. void ArticulationPoints(int n)//Driver Funtion
  48. {
  49. 	ap.clear();
  50. 	rtime=0;//The time for each cycle of DFS
  51. 	for(int i=0;i<n;i++)
  52. 	{
  53. 		parent[i]=-1;//Initializing parents as -1. True for roots
  54. 		visited[i]=0;//All points not visited
  55. 		low[i]=disc[i]=INT_MAX;
  56. 	}
  57. 	for(int i=0;i<n;i++)
  58. 		if(!visited[i])//Vertex not discoverdd
  59. 			DFS(i);
  60. }
  61.  
  62. int main()
  63. {
  64. 	int n,m;//number of vertices, edges
  65. 	cin>>n>>m;
  66. 	for(int i=0;i<m;i++)//Building Graph
  67. 	{
  68. 		int x,y;
  69. 		cin>>x>>y;
  70. 		a[x].pb(y);
  71. 		a[y].pb(x);
  72. 	}
  73. 	ArticulationPoints(n);//Calculating Articulation points
  74. 	cout<<"Articulation Points are:\n";
  75. 	for(int i:ap)
  76. 		cout<<i<<endl;
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 3532KB
comments (?)
stdin 
7 6
0 1
1 2
3 4
2 4
2 6
5 2
stdout 
Articulation Points are:
4
2
2
2
1
https://ideone.com/u5dYOy
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!