fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define int long long
  7. #define mp make_pair
  8. #define ff first
  9. #define ss second
  10. #define pii pair<int,int>
  11. #define INF 100000000000000000
  12. #define EPS 1e-9
  13.  
  14. int n,m,k;
  15. set<int> gr[200011];
  16. vector<int> ans;
  17. bool vis[200011];
  18. pii edge[200011];
  19.  
  20. int32_t main()
  21. {
  22.     cin>>n>>m>>k;
  23.     int x,y;
  24.     for(int i=1;i<=m;i++)
  25.     {
  26.         cin>>x>>y;
  27.         gr[x].insert(y);
  28.         gr[y].insert(x);
  29.         edge[i] = make_pair(x,y);
  30.     }
  31.     queue<int> q;
  32.     set<int> cango;
  33.  
  34.     for(int i=1;i<=n;i++)
  35.     {
  36.         //cout<<gr[i].size()<<"\n";
  37.         if(gr[i].size() < k)
  38.             q.push(i);
  39.         else
  40.             cango.insert(i);
  41.     }
  42.  
  43.     while(!q.empty())
  44.     {
  45.         int x = q.front();
  46.  
  47.         q.pop();
  48.  
  49.         cango.erase(x);
  50.  
  51.         if(vis[x]) continue;
  52.  
  53.         vis[x]=1;
  54.         for(auto c:gr[x])
  55.         {
  56.             gr[x].erase(c);
  57.             gr[c].erase(x);
  58.             if(gr[c].size() < k)
  59.             {
  60.                 cango.erase(c);
  61.                 q.push(c);
  62.             }
  63.         }
  64.     }
  65.     ans.pb(cango.size());
  66.     //cout<<cango.size()<<"\n";
  67.  
  68.     for(int i=m;i>=2;i--)
  69.     {
  70.         int a = edge[i].first;
  71.         int b = edge[i].second;
  72.  
  73.         if(gr[a].find(b) == gr[a].end())
  74.         {
  75.             ans.pb(cango.size());
  76.             //cout<<cango.size()<<"\n";
  77.             continue;
  78.         }
  79.  
  80.         if(gr[b].find(a) == gr[b].end())
  81.         {
  82.             ans.pb(cango.size());
  83.             //cout<<cango.size()<<"\n";
  84.             continue;
  85.         }
  86.  
  87.         q.push(a);
  88.         q.push(b);
  89.  
  90.         gr[a].erase(b);
  91.         gr[b].erase(a);
  92.  
  93.         //cout<<a<<" "<<b<<"\n";
  94.         while(!q.empty())
  95.         {
  96.             int x = q.front();
  97.             q.pop();
  98.             if(gr[x].size() >= k) continue;
  99.  
  100.             if(cango.find(x) == cango.end()) continue;
  101.  
  102.             cango.erase(x);
  103.  
  104.             for(auto c:gr[x])
  105.             {
  106.                 gr[x].erase(c);
  107.                 gr[c].erase(x);
  108.  
  109.                 if(gr[c].size() < k)
  110.                 {
  111.                     //cango.erase(c);
  112.                     q.push(c);
  113.                 }
  114.             }
  115.         }
  116.         ans.pb(cango.size());
  117.         //cout<<cango.size()<<"\n";
  118.     }
  119.  
  120.     for(int i=ans.size()-1;i>=0;i--)
  121.         cout<<ans[i]<<"\n";
  122.     return 0;
  123. }
Success #stdin #stdout 0s 27936KB
comments (?)
stdin
copy 
5 8 2
2 1
4 2
5 4
5 2
4 3
5 1
4 1
3 2
stdout
copy 
0
0
0
3
3
4
4
5
https://ideone.com/B8dFH9
language:
C++14 (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!