Advertisement
Alhiris

Untitled

Feb 23rd, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define pb push_back
  6. #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
  7. #define FORS(i,a,b) for(int i=(a);i<(b);++i)
  8. #define PII pair<int,int>
  9. #define vpp vector<PII>
  10. #define all(x) x.begin(),b.end()
  11. #define SZ(x) ((int)(x).size())
  12. #define ll long long
  13. #define maxn 150005
  14.  
  15. int n;
  16. vector<int> sol[maxn];
  17. int where[maxn];
  18.  
  19. int find(int poz){
  20.     if(poz==where[poz]) return poz;
  21.     return where[poz]=find(where[poz]);//reorientate
  22. }
  23.  
  24. void unite(int a,int b){
  25.     a=find(a);
  26.     b=find(b);
  27.     if(SZ(sol[a])<SZ(sol[b])) swap(a,b);
  28.     for(int x:sol[b])
  29.         sol[a].pb(x);
  30.     where[b]=a;
  31. }
  32.  
  33. int main()
  34. {
  35.     //freopen("pluton.in","r",stdin);
  36.     //freopen("pluton.out","w",stdout);
  37.     int x,y;
  38.     cin>>n;
  39.     FOR(i,1,n)
  40.         where[i]=i,sol[i].pb(i);
  41.     FORS(i,1,n){
  42.         cin>>x>>y;
  43.         unite(x,y);
  44.     }
  45.     for(int a:sol[find(1)]) cout<<a<<' ';
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement