fork download 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(1e6)+7;
  14.  
  15. int n , q , res;
  16. vector<int> g[maxN];
  17. bool vis[maxN];
  18. vector<ii> E;
  19.  
  20. struct DSU{
  21.     int fa[maxN] , cnt[maxN];
  22.     bool cycle;
  23.  
  24.     void reset(){
  25.         cycle = 0;
  26.         for (int i = 1 ; i <= n ; i++) fa[i] = -1 , cnt[i] = 0;
  27.     }
  28.  
  29.     int root(int x){
  30.         if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
  31.     }
  32.  
  33.     void unite(int u , int v){
  34.         cnt[u]++;
  35.         cnt[v]++;
  36.         if (cnt[u] > 2) cycle = 1;
  37.         if (cnt[v] > 2) cycle = 1;
  38.         u = root(u);
  39.         v = root(v);
  40.         if (u == v){
  41.             cycle = 1;
  42.             return;
  43.         }
  44.         if (-fa[u] < -fa[v]) swap(u , v);
  45.         fa[u] += fa[v];
  46.         fa[v] = u;
  47.     }
  48.  
  49.     int get(int x){
  50.         return -fa[root(x)];
  51.     }
  52. } A , f[4];
  53.  
  54. vector<int> ver;
  55.  
  56. void solve(){
  57.     cin >> n >> q;
  58.     res = n;
  59.     bool check = 0;
  60.     A.reset();
  61.     for (int i = 0 ; i < 4 ; i++) f[i].reset();
  62.     int num_cycle = 0;
  63.     while (q--){
  64.         int u , v;
  65.         cin >> u;
  66.         if (u == -1){
  67.             cout << res << " ";
  68.         }
  69.         else{
  70.             cin >> v;
  71.             if (res == 0) continue;
  72.             if (check == 1){
  73.                 res = 0;
  74.                 for (int i = 0 ; i < sz(ver) ; i++){
  75.                     if (u != ver[i] && v != ver[i]){
  76.                         f[i].unite(u , v);
  77.                     }
  78.                     res += 1 - f[i].cycle;
  79.                 }
  80.             }
  81.             else{
  82.                 g[u].push_back(v);
  83.                 g[v].push_back(u);
  84.                 E.push_back({u , v});
  85.                 if (sz(g[u]) < sz(g[v])) swap(u , v);
  86.                 if (sz(g[u]) == 3){
  87.                     res = 0;
  88.                     ver = g[u]; ver.push_back(u);
  89.                     for (int i = 0 ; i < sz(ver) ; i++){
  90.                         for (auto it : E){
  91.                             int u = it.fi;
  92.                             int v = it.se;
  93.                             if (u != ver[i] && v != ver[i]) f[i].unite(u , v);
  94.                         }
  95.                         res += 1 - f[i].cycle;
  96.                     }
  97.                     check = 1;
  98.                 }
  99.                 else{
  100.                     if (A.root(u) == A.root(v)){
  101.                         num_cycle++;
  102.                         res = A.get(u);
  103.                     }
  104.                     A.unite(u , v);
  105.                     if (num_cycle == 2) res = 0;
  106.                 }
  107.             }
  108.         }
  109.     }
  110. }
  111.  
  112. #define name "rings"
  113.  
  114. int main(){
  115.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  116.     if (fopen(name".INP" , "r")){
  117.         freopen(name".INP" , "r" , stdin);
  118.         freopen(name".OUT" , "w" , stdout);
  119.     }
  120.     int t = 1; cin >> t;
  121.     solve();
  122.     return 0;
  123. }
  124.  
  125.  
Success #stdin #stdout 0.01s 36936KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/66PomS
language:
C++14 (gcc 8.3)
created:
2 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!