CF1131F

Purslane · 2023-09-25 19:36:00 · 题解

Solution

迷惑。

考虑直接模拟，如果有 x y 的要求，直接把 x 所在块和 y 所在块拼在一起。很显然，无论谁在前谁在后都不会对后面产生影响。

因此你在并查集的每个父亲节点记一下链表的首尾即可。

代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,nxt[MAXN],fa[MAXN],hd[MAXN],tl[MAXN];
int find(int k) {
    if(fa[k]==k) return k;
    return fa[k]=find(fa[k]);   
}
void merge(int u,int v) {
    u=find(u),v=find(v);
    nxt[tl[u]]=hd[v],tl[u]=tl[v],fa[v]=u;
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n; ffor(i,1,n) fa[i]=i,hd[i]=tl[i]=i;
    ffor(i,1,n-1) {
        int x,y;
        cin>>x>>y;
        merge(x,y); 
    }
    int st=hd[find(1)];
    ffor(i,1,n) {
        cout<<st<<' ';
        st=nxt[st]; 
    }
    return 0;
}

所以这是紫题。不会有人用块状链表或平衡树吧 /jy