SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*#pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")*/
  5. #include <stdio.h>
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define vec vector
  10. #define pb push_back
  11. #define all(x) x.begin(), x.end()
  12. #define rall(x) x.rbegin(), x.rend()
  13. #define Str(x) to_string(x)
  14. #define len(s) (int)s.size()
  15. #define int long long
  16. typedef long long ll;
  17. typedef double d;
  18. typedef long double lld;
  19. typedef string str;
  20. typedef unsigned long long ull;
  21. typedef unsigned int ui;
  22.  
  23. const int MAXN = 160000;
  24.  
  25.  
  26. vector <int> fck[MAXN], rt(MAXN), cnt(MAXN, 1);
  27.  
  28. int get(int x)
  29. {
  30.     return x == rt[x] ? x : rt[x] = get(rt[x]);
  31. }
  32.  
  33. void Union(int x, int y)
  34. {
  35.     x = get(x);
  36.     y = get(y);
  37.     if (cnt[x] < cnt[y])
  38.         swap(x, y);
  39.     for (auto it : fck[y])
  40.         fck[x].pb(it);
  41.     fck[y].clear();
  42.     cnt[x] += cnt[y];
  43.     cnt[y] = 0;
  44.     rt[y] = x;
  45. }
  46.  
  47. main()
  48. {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.     cout.tie(NULL);
  52. #ifdef LOCAL
  53.     freopen("input.txt", "r", stdin);
  54.     freopen("output.txt", "w", stdout);
  55. #endif
  56.     int n;
  57.     cin >> n;
  58.     for (int i = 0; i < n; i++)
  59.     {
  60.         rt[i] = i;
  61.         fck[i].pb(i);
  62.     }
  63.     for (int i = 0; i < n - 1; i++)
  64.     {
  65.         int x, y;
  66.         cin >> x >> y;
  67.         x--;
  68.         y--;
  69.         Union(x, y);
  70.     }
  71.     for (int  i =0 ; i < n; i++)
  72.     {
  73.         if (cnt[i] == n)
  74.         {
  75.             for (auto it : fck[i])
  76.                 cout << it + 1<< " ";
  77.         }
  78.     }
  79.     return 0;
  80. }
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