SHARE
TWEET

Untitled

a guest Dec 3rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct var{
  6.     int x, y;
  7. } mu[500001];
  8.  
  9. int t[100001], h[100001], c1, c2, m, n, sol[500001];
  10.  
  11. int Find(int x)
  12. {
  13.     if(t[x]!=0)
  14.         return Find(t[x]);
  15.      return x;
  16. }
  17.  
  18. void Union(int x,int y)
  19. {
  20.     if(h[x]==h[y])
  21.     {
  22.         t[x]=y;
  23.         h[y]++;
  24.     }
  25.     else
  26.         if(h[x]<h[y])
  27.             t[x]=y;
  28.         else
  29.             t[y]=x;
  30. }
  31. int x, y;
  32. int main() {
  33.  
  34.     cin >> n >> m;
  35.     for(int i = 1; i <= m; ++i) {
  36.         cin >> mu[i].x >> mu[i].y;
  37.     }
  38.     for(int i = m; i >= 1; --i) {
  39.         sol[i] = n;
  40.         c1 = Find(mu[i].x);
  41.         c2 = Find(mu[i].y);
  42.         if(c1 != c2)
  43.             --n, Union(c1, c2);
  44.     }
  45.     for(int i = 1; i <= m; ++i)
  46.         cout << sol[i] << '\n';
  47.     return 0;
  48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top