题解：P10657 BZOJ4998 星球联盟

AN6M · 2025-02-26 20:13:23 · 题解

我的做法不同于清一色的 LCT，只需要用到最小生成树和并查集。

考虑把每条边赋一个权值 t 表示加入图的时间，从这张图上扯出一个最小生成树森林。

考虑依次在树上加边，对于一条要加入的边可以暴力往上加边，对于每一条树边第一次加入的必然是它本身。在第二次加边的时候就形成了环，可以用并查集合并两个节点。由于每条边最多加两次，所以总复杂度可以做到 O(n\alpha(n))。

这里偷懒写了一个 O(n\log n) 的写法。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200010
int n,m,q,tot,fa[N],dep[N],siz[N],trfa[N],s[N],sum[N];
bool vis[N];
struct stu{
    int u,v,tim;
    friend bool operator<(stu a,stu b){
        return a.tim<b.tim;
    }
}e[N<<1],ask[N],g[N];
vector<int>to[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y){
        return;
    }
    if(siz[x]<siz[y]){
        swap(x,y);
    }
    fa[y]=x;
    siz[x]+=siz[y];
    sum[x]+=sum[y];
}
void mergetofa(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y){
        return;
    }
    fa[y]=x;
    sum[x]+=sum[y];
}
void dfs(int x,int fa){
    vis[x]=1;
    trfa[x]=fa;
    dep[x]=dep[fa]+1;
    for(int i=0;i<to[x].size();i++){
        int y=to[x][i];
        if(y==fa){
            continue;
        }
        dfs(y,x);
    }
}
void MERGE(int x,int y){
    if(find(x)==find(y)){
        return;
    }
    x=find(x);
    y=find(y);
    while(find(y)!=find(x)){
        if(dep[find(x)]>dep[find(y)]){
            swap(x, y);
        }
        if(!s[y]){
            s[y]++;
        }
        else{
            mergetofa(find(trfa[y]),y);
        }
        y=find(trfa[y]);
    }
}
signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=m;i++){
        tot++;
        cin>>e[tot].u>>e[tot].v;
        e[tot].tim=0;
        // cout<<e[tot].u<<' '<<e[tot].v<<' '<<e[tot].tim<<'\n';
        g[i]=e[tot];
    }
    for(int i=1;i<=q;i++){
        cin>>ask[i].u>>ask[i].v;
        ask[i].tim=i;
        e[++tot]=ask[i];
        // cout<<e[tot].u<<' '<<e[tot].v<<' '<<e[tot].tim<<'\n';
    }
    int added=0;
    sort(e+1,e+tot+1);
    for(int i=1;i<=tot;i++){
        if(added==n-1){
            break;
        }
        int x=find(e[i].u),y=find(e[i].v);
        if(x==y){
            continue;
        }
        merge(x,y);
        added++;
        to[e[i].u].push_back(e[i].v);
        to[e[i].v].push_back(e[i].u);
        // cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].tim<<'\n';
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
        sum[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i,0);
        }
    }
    // for(int i=1;i<=n;i++){
    //     cout<<trfa[i]<<' ';
    // }
    // cout<<'\n';
    for(int i=1;i<=m;i++){
        int x=find(g[i].u),y=find(g[i].v);
        MERGE(x,y);
    }
    for(int i=1;i<=q;i++){
        int x=find(ask[i].u),y=find(ask[i].v);
        if(x==y){
            cout<<sum[x]<<'\n';
            continue;
        }
        MERGE(x,y);
        x=find(ask[i].u),y=find(ask[i].v);
        if(x==y){
            cout<<sum[x]<<'\n';
        }
        else{
            cout<<"No\n";
        }
    }
    return 0;
}

练习：https://www.luogu.com.cn/problem/P6351