Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement