cf1131f 构造+并查集

#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]<<" ";
}