Codeforces Round #541 (Div. 2) F. Asya And Kittens(并查集+邻接表)
题目链接：https://codeforces.com/contest/1131/problem/F
题意是有n个数，有n-1种关系，最终会构成一颗树，从根节点按顺序输出这n个点，其实看图就理解的差不多了。
思路就是按题意将所要连的两个链表merge一下就好了，不太好描述，看代码画画图就理解了。
AC代码：
#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;
}
