fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int graph[1001][1001];
  4. int visit[1001];
  5. int dis[1001], low[1001];
  6. bool isAP[1001];
  7. int timer = 0;
  8. int n, e;
  9.  
  10. void DFS(int u, int parent)
  11. {
  12.     visit[u] = 1;
  13.     dis[u] = low[u] = ++timer;
  14.  
  15.     int child = 0;
  16.     for(int v = 1; v <= n; v++)
  17.     {
  18.         if(visit[v]==0 && graph[u][v]!=0)
  19.         {
  20.             child++;
  21.             DFS(v, u);
  22.  
  23.             low[u] = min(low[u], low[v]);
  24.  
  25.             if(parent != -1 && dis[u] <= low[v])
  26.             {
  27.                 isAP[u] = true;
  28.             }
  29.         }
  30.  
  31.         else if(v != parent && graph[u][v] != 0)
  32.         {
  33.             low[u] = min(low[u], dis[v]);
  34.         }
  35.     }
  36.  
  37.     if(parent == -1 && child > 1)
  38.     {
  39.         isAP[u] = true;
  40.     }
  41.  
  42. }
  43.  
  44. int main()
  45. {
  46.     cin>>n>>e;
  47.     int u, v;
  48.     for(int i = 1; i <= e; i++)
  49.     {
  50.         cin>>u>>v;
  51.         graph[u][v] = 1;
  52.         graph[v][u] = 1;
  53.     }
  54.     DFS(1, -1);
  55.  
  56.     for(int i = 1; i <= n; i++)
  57.     {
  58.         if(isAP[i] ==  true)
  59.         {
  60.             cout<<i<<" is an AP"<<endl;
  61.         }
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
10 13
1 4
1 2
3 4
2 3
3 9
3 10
2 5
5 6
5 7
5 8
2 7
2 8
7 8
stdout 
2 is an AP
3 is an AP
5 is an AP
https://ideone.com/k7K6p6
language:
C++ (gcc 8.3)
created:
9 days 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!