fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int time1=0;
  4. class Graph {
  5.     public:
  6.     int V;
  7.     list<int> *adj;
  8.     public:
  9.     Graph(int);
  10.     void addedge(int,int);
  11.     void printgraph(int);
  12.     //void findartpt(int,bool[],int[],map<int,int>,map<int,int>,vector<int>);
  13.     void findartpt(int,bool[],int[],int[],int[],bool[]);
  14.  
  15. };
  16. Graph::Graph(int v)  {
  17.     this->V=v;
  18.     //for(int i=0;i<v;i++)
  19.     adj=new list<int>[v];
  20. }
  21. void Graph::addedge(int u,int v)    {
  22.     adj[v].push_back(u);
  23.     adj[u].push_back(v);
  24. }
  25. void Graph::printgraph(int n)    {
  26.     for(int i=0;i<n;i++)    {
  27.         for(auto it:adj[i]) {
  28.             cout<<it<<" ";
  29.         }
  30.         cout<<endl;
  31.     }
  32.     cout<<endl;
  33. }
  34. // void Graph::findartpt(int v,bool visited[],int parent[],map<int,int> lowtime,map<int,int> vistime,vector<int> artpts)    {
  35. //     visited[v]=false;
  36. //     //vistime.push_back();
  37. //     lowtime[v]=time1+1;
  38. //     vistime[v]=time1+1;
  39. //     time1++;
  40. //     int child=0;
  41. //     bool isartpt=false;
  42. //     for(auto it: adj[v])    {
  43. //         /*if(parent[v]==it)
  44. //             continue;
  45. //         else    {*/
  46. //             if(!visited[it])    {
  47. //                 child++;
  48. //                 parent[it]=v;
  49. //                 findartpt(v,visited,parent,lowtime,vistime,artpts);
  50. //                 /*if(vistime[v]<=lowtime[it])
  51. //                     isartpt=true;
  52. //                 else    
  53. //                     lowtime[v]=min(lowtime[v],lowtime[it]);
  54. //             }
  55. //             else    
  56. //                 lowtime[v]=min(lowtime[v],vistime[it]);
  57. //         }
  58. //     }
  59. //     if((parent[v]==-1 && child>=2) || (parent[v]!=-1 && isartpt==true))
  60. //         artpts.push_back(v);*/
  61.  
  62.  
  63.  
  64. //                 lowtime[v]  = min(lowtime[v], lowtime[it]); 
  65.  
  66. //             // u is an articulation point in following cases 
  67.  
  68. //             // (1) u is root of DFS tree and has two or more chilren. 
  69. //             if (parent[v] == -1 && child > 1) 
  70. //                artpts.push_back(v);
  71. //                //ap[u] = true; 
  72.  
  73. //             // (2) If u is not root and low value of one of its child is more 
  74. //             // than discovery value of u. 
  75. //             if (parent[v] != -1 && lowtime[it] >= vistime[v]) 
  76. //                artpts.push_back(v);
  77. //                //ap[u] = true; 
  78. //         } 
  79.  
  80. //         // Update low value of u for parent function calls. 
  81. //         else if (it != parent[v]) 
  82. //             lowtime[v]  = min(lowtime[v], vistime[it]); 
  83. //     } 
  84. // }
  85. void Graph::findartpt(int v,bool visited[],int parent[],int lowtime[],int vistime[],bool artpts[])    {
  86.     visited[v]=true;
  87.     //vistime.push_back();
  88.     lowtime[v]=time1+1;
  89.     vistime[v]=time1+1;
  90.     time1++;
  91.     int child=0;
  92.     bool isartpt=false;
  93.     for(auto it: adj[v])    {
  94.         /*if(parent[v]==it)
  95.             continue;
  96.         else    {*/
  97.             if(!visited[it])    {
  98.                 child++;
  99.                 parent[it]=v;
  100.                 findartpt(v,visited,parent,lowtime,vistime,artpts);
  101.                 /*if(vistime[v]<=lowtime[it])
  102.                     isartpt=true;
  103.                 else    
  104.                     lowtime[v]=min(lowtime[v],lowtime[it]);
  105.             }
  106.             else    
  107.                 lowtime[v]=min(lowtime[v],vistime[it]);
  108.         }
  109.     }
  110.     if((parent[v]==-1 && child>=2) || (parent[v]!=-1 && isartpt==true))
  111.         artpts.push_back(v);*/
  112.  
  113.  
  114.  
  115.                 lowtime[v]  = min(lowtime[v], lowtime[it]); 
  116.  
  117.             // u is an articulation point in following cases 
  118.  
  119.             // (1) u is root of DFS tree and has two or more chilren. 
  120.             if (parent[v] == -1 && child > 1) 
  121.                artpts[v] = true; 
  122.  
  123.             // (2) If u is not root and low value of one of its child is more 
  124.             // than discovery value of u. 
  125.             if (parent[v] != -1 && lowtime[it] >= vistime[v]) 
  126.                artpts[v] = true; 
  127.         } 
  128.  
  129.         // Update low value of u for parent function calls. 
  130.         else if (it != parent[v]) 
  131.             lowtime[v]  = min(lowtime[v], vistime[it]); 
  132.     } 
  133. }
  134.  
  135. int main()  {
  136.     int v,v1,v2,e,i;
  137.     cout<<"Enter the number of vertices in the graph: "<<endl;
  138.     cin>>v;
  139.     Graph g(v);
  140.     cout<<"Enter the number of edges: "<<endl;
  141.     cin>>e;
  142.     for(i=0;i<e;i++)    {
  143.         cin>>v1;
  144.         cin>>v2;
  145.         g.addedge(v1,v2);
  146.     }
  147.     //g.printgraph(v);
  148.     //map<int,int> vistime,lowtime;
  149.     int *vistime=new int[v];
  150.     int *lowtime=new int[v];
  151.     //int *lowtime[v],*vistime[v];
  152.     //vector<int> artpts;
  153.     bool *artpts=new bool[v];
  154.     int *parent=new int[v];
  155.     bool *visited=new bool[v];
  156.     for(i=0;i<v;i++)    {
  157.         visited[i]=false;
  158.         parent[i]=-1;
  159.         artpts[i]=false;
  160.     }
  161.     for(i=0;i<v;i++)    {
  162.         if(visited[i]==false)
  163.            g.findartpt(i,visited,parent,lowtime,vistime,artpts);
  164.     }
  165.     for(i=0;i<v;i++)    {
  166.         if(artpts[i]==true)
  167.            cout<<i<<" ";
  168.     }
  169.     //for(auto it=artpts.begin();it!=artpts.end();it++)
  170.     //    cout<<*it<<" ";
  171.     cout<<endl;
  172. }
Internal error #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
5
5
1 0
0 2
2 1
0 3
3 4
stdout
copy 
Standard output is empty
https://ideone.com/XA547t
language:
C++ (gcc 8.3)
created:
4 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!