P10875 [COTS 2022] 游戏 M 题解

· · 题解

题解区都是很厉害的做法，但是我太菜了。

考虑直接用并查集维护边双，先拉出一棵 MST 出来，然后把树边全扬了，接下来就是一些非树边，我们考虑用这些边去做链覆盖，显然地，如果两个点之间每一条边都被覆盖了，那此时一定在一个点双内。用并查集维护一下就没了。

但是我们还要查询，直接把询问 (u,v) 挂在 u,v 两个点上，同时开一个 vector 存一个边双里面所有的询问，每次上面做一次有效覆盖的时候，就相当于连通两个边双，启发式合并同时处理跨这两个边双的询问即可，正确性显然。

因为每个询问最多被启发式合并 \log n 次，所以复杂度 O(q\log q)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int n,m,q,tm;
int uu[300005];
int vv[300005];
int ff[300005];
int fa[300005];
bool mp[300005];
int dfn[300005];
int out[300005];
int ans[300005];
vector <int> e[300005];
struct node{int u,v,id;};
vector <node> g[300005];

inline int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

inline void dfs(int u,int f){
    ff[u]=f;
    dfn[u]=++tm;
    for(int v:e[u]) if(v^f) dfs(v,u);
    out[u]=tm;
    return ;
}

inline void merge(int u,int v,int k){
    if(g[v].size()<g[u].size()) swap(g[u],g[v]);
    for(auto tmp:g[u]){
        int uu=Find(tmp.u),vv=Find(tmp.v);
        if((uu==u&&vv==v)||(uu==v&&vv==u)) ans[tmp.id]=k;
        else g[v].emplace_back(tmp);
    }
    return ;
}

inline void Cover(int u,int v,int k){
    int l=min(dfn[u],dfn[v]),r=max(out[u],out[v]);
    int pos=Find(u);
    while(dfn[pos]>l||out[pos]<r){
        merge(pos,Find(ff[pos]),k);
        fa[pos]=Find(ff[pos]);
        pos=Find(ff[pos]);
    }
    pos=Find(v);
    while(dfn[pos]>l||out[pos]<r){
        merge(pos,Find(ff[pos]),k);
        fa[pos]=Find(ff[pos]);
        pos=Find(ff[pos]);
    }
    return ;
}

int main(){
    in(n),in(m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) in(uu[i]),in(vv[i]);
    for(int i=1;i<=m;i++){
        int u=Find(uu[i]),v=Find(vv[i]);
        if(u==v) mp[i]=1;
        else{
            e[uu[i]].emplace_back(vv[i]);
            e[vv[i]].emplace_back(uu[i]);
            fa[u]=v;
        }
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);
    in(q);
    for(int i=1;i<=q;i++){
        ans[i]=-1;
        int u,v;
        in(u),in(v);
        g[u].push_back({u,v,i});
        g[v].push_back({u,v,i});
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        if(!mp[i]) continue;
        Cover(uu[i],vv[i],i);
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

    return 0;
}