fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstring>
  5. #define MAX 10003
  6. using namespace std;
  7.  
  8. vector<int>G[MAX];
  9. int low[MAX],d[MAX],visited[MAX],cutpoint[MAX],dtime;
  10. pair<int,int>result[MAX];
  11.  
  12. bool compare(pair<int,int>a,pair<int,int>b)
  13. {
  14.     if(a.second==b.second)
  15.     return a.first<b.first;
  16.     return a.second>b.second;
  17. }
  18. void DFS(int u,int parent =-1)
  19. {
  20.     int i,v,child=0;
  21.     bool art=false;
  22.     low[u]=d[u]=visited[u]=++dtime;
  23.     for(i=0;i<G[u].size();++i)
  24.     {
  25.         v=G[u][i];
  26.         if(v==parent)
  27.         continue;
  28.         if(visited[v])
  29.         low[u]=min(low[u],d[v]);
  30.         else
  31.         {
  32.             DFS(v,u);
  33.             ++child;
  34.             low[u]=min(low[u],low[v]);
  35.             if(low[v]>=d[u])
  36.                 art=true;
  37.         }
  38.     }
  39.     if(art&&parent>-1)
  40.     cutpoint[u]=child+1;
  41.     else
  42.     cutpoint[u]=1;
  43.     if(parent==-1&&child>1)
  44.     cutpoint[u]=child;
  45. }
  46.  
  47. int main()
  48. {
  49.     int n,m,i,a,b;
  50.     while(cin>>n>>m,n)
  51.     {
  52.         memset(low,0,sizeof(low));
  53.         memset(d,0,sizeof(d));
  54.         memset(visited,0,sizeof(visited));
  55.         memset(cutpoint,0,sizeof(cutpoint));
  56.         for(i=0;i<=n;++i)
  57.         G[i].clear();
  58.         while(cin>>a>>b,a!=-1)
  59.         {
  60.             G[a].push_back(b);
  61.             G[b].push_back(a);
  62.         }
  63.         dtime=0;
  64.         DFS(0);
  65.         for(i=0;i<n;++i)
  66.         {
  67.             result[i].first=i;
  68.             result[i].second=cutpoint[i];
  69.         }
  70.         sort(result,result+n,compare);
  71.         for(i=0;i<m;++i)
  72.         cout<<result[i].first<<" "<<result[i].second<<endl;
  73.     }
  74.     return 0;
  75. }
Runtime error #stdin #stdout 0s 3208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MwtPqn
language:
C++ (gcc 8.3)
created:
10 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!