fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using pi=pair<int,int>;
  5.  
  6. long long K(long long x){
  7.   return (x*(x-1))/2;
  8. }
  9.  
  10. int main(){
  11.   ios::sync_with_stdio(false);
  12.   cin.tie(nullptr);
  13.   int n,m;
  14.   cin >> n >> m;
  15.   vector<pi> eg(m);
  16.   vector<int> deg(n,0);
  17.   for(auto &nx : eg){
  18.     cin >> nx.first;
  19.     cin >> nx.second;
  20.     nx.first--;
  21.     nx.second--;
  22.     deg[nx.first]++;
  23.     deg[nx.second]++;
  24.   }
  25.  
  26.   vector<int> vn(n,0);
  27.   for(int i=0;i<n;i++){
  28.     vn[deg[i]]++;
  29.   }
  30.   for(int i=n-2;i>=0;i--){
  31.     vn[i]+=vn[i+1];
  32.   }
  33.   vector<int> cnt(n,0);
  34.   for(auto &nx : eg){
  35.     cnt[min(deg[nx.first],deg[nx.second])]++;
  36.   }
  37.   for(int i=n-2;i>=0;i--){
  38.     cnt[i]+=cnt[i+1];
  39.   }
  40.  
  41.   int kdeg=1e9;
  42.   for(int i=0;i<n;i++){
  43.     if(cnt[i]==K(vn[i])){kdeg=i; break;}
  44.   }
  45.   if(kdeg>5e8){cout << "0\n"; return 0;}
  46.  
  47.   vector<int> col(n,0);
  48.   for(int i=0;i<n;i++){
  49.     if(deg[i]>=kdeg){col[i]=1;}
  50.   }
  51.  
  52.   bool jud=true;
  53.   int c11=0;
  54.   vector<int> speg(n,0);
  55.   for(auto &nx : eg){
  56.     if(col[nx.first]==1 && col[nx.second]==1){c11++;}
  57.     else if(col[nx.first]==0 && col[nx.second]==0){jud=false; break;}
  58.     else{
  59.       speg[nx.first]++;
  60.       speg[nx.second]++;
  61.     }
  62.   }
  63.   if(!jud){cout << "0\n"; return 0;}
  64.  
  65.   int spsz=0;
  66.   for(auto &nx : col){spsz+=nx;}
  67.  
  68.   int res=1;
  69.   for(int i=0;i<n;i++){
  70.     if(col[i]==0){
  71.       if(speg[i]==spsz){res++;}
  72.     }
  73.     else{
  74.       if(speg[i]==0){res++;}
  75.     }
  76.   }
  77.   cout << res << "\n";
  78.   return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
3 3
1 3
1 2
2 3
stdout 
4
https://ideone.com/Xb0HFN
language:
C++14 (gcc 8.3)
created:
96 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!