fork download
copy 
  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 j = 1; j <= n; j++)
  17.     {
  18.         if(visit[j]==0 && graph[u][j]!=0)
  19.         {
  20.             child++;
  21.             DFS(j, u);
  22.  
  23.             low[u] = min(low[u], low[j]);
  24.  
  25.             if(parent != -1 && dis[u] <= low[j])
  26.             {
  27.                 isAP[u] = true;
  28.             }
  29.         }
  30.  
  31.         else if(j != parent && graph[u][j] != 0)
  32.         {
  33.             low[u] = min(low[u], dis[j]);
  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 5324KB
comments (?)
stdin
copy 
6 7
1 4
1 2
4 3
2 3
3 5
3 6
5 6
stdout
copy 
3 is an AP
https://ideone.com/29vHB3
language:
C++ (gcc 8.3)
created:
15 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!