fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void dfs(int i);
  5. void scanit(int &i)
  6. {
  7.     i=0;
  8.     register int c=getchar();
  9.     for(;c>'9'||c<'0';c=getchar());
  10.     for(;c>='0'&&c<='9';c=getchar())
  11.         i=(i<<1)+(i<<3)+c-'0';
  12. }
  13.  
  14. vector<vector<int> > V;
  15. vector<int> vis;
  16. vector<int> ans;
  17.  
  18. int main(void)
  19. {
  20.     int t,i,m,n,u,v;
  21.     scanit(t);
  22.     while(t--)
  23.     {
  24.         scanit(n);
  25.         scanit(m);
  26.         V.resize(n+1,vector<int>(0));
  27.         vis.resize(n+1);
  28.         ans.resize(n,0);
  29.         for(i=0;i<m;i++)
  30.         {
  31.             scanit(u);
  32.             scanit(v);
  33.             V[u].push_back(v);
  34.             V[v].push_back(u);
  35.         }
  36.         //for(i=0;i)
  37.         for(i=1;i<n;i++)
  38.         {
  39.             if(vis[i]==0)
  40.             {
  41.                 if(i!=1)
  42.                     ans[0]++;
  43.                 dfs(i);
  44.             }
  45.         }
  46.         for(i=1;i<n;i++)
  47.             ans[i]+=ans[i-1];
  48.         for(i=0;i<n;i++)
  49.             printf("%d ",ans[i]);
  50.         printf("\n");
  51.         vis.clear();
  52.         ans.clear();
  53.         V.clear();
  54.     }
  55. }
  56.  
  57. void dfs(int i)
  58. {
  59.     stack<int> s;
  60.     s.push(i);
  61.    // cout<<i<<' '<<S[i]<<' '<<V[i].size()<<endl;
  62.     while(s.empty()==0)
  63.     {
  64.         int j=s.top();
  65.         //cout<<j<<' '<<V[j].size()<<' '<<V[k].size()<<endl;
  66.         s.pop();
  67.         vis[j]=1;
  68.         for(vector<int>::iterator it=V[j].begin();it!=V[j].end();it++)
  69.         {
  70.             if(vis[*it]==0)
  71.             {
  72.                 //cout<<j<<' '<<*it<<' '<<V[j].size()<<' '<<V[*it].size()<<endl;
  73.                 if(V[*it].size()>V[j].size())
  74.                     ans[V[j].size()]++;
  75.                 else
  76.                     ans[V[(*it)].size()]++;
  77.                 s.push(*it);
  78.             }
  79.         }
  80.     }
  81. }
  82.  
Time limit exceeded #stdin #stdout 5s 16056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/raYtCB
language:
C++ (gcc 8.3)
created:
6 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!