#include<bits/stdc++.h>
using namespace std;
#define maxn 150005
int f[maxn],n;
vector<
int>
ans[maxn];
int find(
int x){
return f[x]==-
1?x:f[x]=
find(f[x]);
}
void bing(
int u,
int v){
//把v联通块并到u中去
for(
int i=
0;i<ans[v].size();i++
)
ans[u].push_back(ans[v][i]);
f[v]=
u;
ans[v].clear();
}
int main(){
cin>>
n;
memset(f,-
1,
sizeof f);
for(
int i=
1;i<=n;i++
)ans[i].push_back(i);
for(
int i=
1;i<n;i++
){
int u,v;
cin>>u>>
v;
v=find(v),u=
find(u);
if(ans[v].size()>
ans[u].size())
swap(u,v);
bing(u,v);
}
int id;
for(
int i=
1;i<=n;i++
)
if(f[i]==-
1)id=
i;
for(
int i=
0;i<ans[id].size();i++
)
cout<<ans[id][i]<<
" ";
}
转载于:https://www.cnblogs.com/zsben991126/p/10480417.html
