题解：AT_arc045_d [ARC045D] みんな仲良し高橋君

· · 题解

另一篇题解在这说啥呢。咋还扯到圆方树上去了，算了写个方便点的。

先考虑单组询问怎么做。

首先遇到 (x,y) 这种形式，然后操作只和一边有关，有一个经典的套路是，建立一个二分图，然后遇到一个 (x,y)，就把 x^L 向 y^R 连一条边。

观察一下发生了什么：有一张 2n 条边的二部图，每次可以删除一个点相邻的两条边，判是否能把图删完。

不难猜到，这等价于每个连通块的边数都是偶数。证明考虑归纳（是一个小清新构造捏）。

之后，就等价于，给你一个 2n+1 条边的图，求删每条边后是否能满足每个连通块的边数都是偶数。

先用并查集找出所有极大连通块，然后分类讨论：

因为连通，所以可以找到一个 dfs 树，那么所有非树边都是返祖边。删除了它不会改变连通性，因此这样的边一定都是 ok 的。

接下来看树边。第一种情况，删掉这条边后不会改变连通性，那么也一定 ok，这个可以拿 dep 和 low 来判。

第二种情况，会改变，那么这条边是一个桥，实际上，只需要维护一个子树边数奇偶性就好了。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
int fa[400005],cnt[400005],bh[400005];
int findfather(int x){
    return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
int x[200005],y[200005],ok[200005];
vector<pair<int,int>>g[400005];
int vist[400005],dep[400005],low[400005];
int sz[400005],vv[400005];
void dfs1(int x,int la){
    vist[x]=1;sz[x]=1;low[x]=dep[x];
    for(auto pi:g[x]){
        int cu=pi.first,c2=pi.second;
        if(c2==la)continue;
        if(vist[cu]){
            if(dep[cu]>dep[x])continue;
            low[x]=min(low[x],dep[cu]);
            ++sz[x];ok[c2]=1;
            continue;
        }
        dep[cu]=dep[x]+1;vv[cu]=c2;
        dfs1(cu,c2);
        low[x]=min(low[x],low[cu]);
        sz[x]=sz[x]+sz[cu];
    }
}
void dfs2(int x){
    for(auto pi:g[x]){
        int cu=pi.first,c2=pi.second;
        if(vv[cu]!=c2)continue;
        if(low[cu]<dep[cu]||sz[cu]%2)ok[c2]=1;
        dfs2(cu);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    int m=2*n+1;
    for(int i=1;i<=2*m;++i)fa[i]=i,cnt[i]=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x[i],&y[i]);
        int u=x[i],v=2*n+1+y[i];
        int fu=findfather(u),fv=findfather(v);
        if(fu!=fv)fa[fu]=fv,cnt[fv]+=cnt[fu];
        ++cnt[fv];
    }
    int gs=0,wz=0;
    for(int i=1;i<=2*m;++i)if(fa[i]==i){
        if(cnt[i]&1)++gs,wz^=i;
    }
    if(gs==1){
        int t=0;
        for(int i=1;i<=2*m;++i)if(findfather(i)==wz){
            bh[i]=++t;
        }
        for(int i=1;i<=m;++i)if(fa[x[i]]==wz){
            int u=bh[x[i]],v=bh[m+y[i]];
            g[u].emplace_back(v,i);
            g[v].emplace_back(u,i);
        }
        dfs1(bh[wz],0);
        dfs2(bh[wz]);
    }
    for(int i=1;i<=m;++i)puts(ok[i]?"OK":"NG");
    return 0;
}