Codeforces Round #541 (Div. 2) F. Asya And Kittens(并查集+邻接表)

#include <bits/stdc++.h>
#define maxn 150005
using namespace std;
int pre[maxn];
int n;
vector<int> v[maxn];

void init(){
  for(int i=0;i<=n;i++){
    pre[i] = i;
  }
}

void dfs(int x){
  printf("%d ", x);
  for(int i=0;i<v[x].size();i++) dfs(v[x][i]);
}

int Find(int x){
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
    v[fx].push_back(fy);
  }
}

int main()
{
  scanf("%d",&n);
  init();
  for(int i=1;i<n;i++){
    int u, v;
    scanf("%d%d",&u, &v);
    merge(u, v);
  }
  dfs(Find(1));
  return 0;
}