自动搬运

查看原文

来自洛谷，原作者为

	devout 想要变得可爱qwq | AFO

搬运于2025-08-24 23:09:40，当前版本为作者最后更新于2025-05-13 14:40:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

有一个图，问是否能删不超过两条边使得它变成一个二分图，如果不可以输出0，否则输出删除边数最少得方案数。

题目解答

发现这个图几乎是一个二分图，所以可以考虑先做一个二分图染色，得到了一棵 dfs 树，这棵树的非树边一定是返祖边。一条非树边可以和树边形成一个环，如果是奇环则称其为奇边，否则称其为偶边，显然如果没有奇边则直接输出 $1$ 即可。

设 $S$ 为所有奇边的集合对每条边 $e$，若 $e$ 是一条非树边，则 $T(e)=\{e\}$，否则设 $e=(u,fa_u)$，定义 $T(e)$ 是所有 $u$ 子树到 $u$ 子树外的返祖边的集合。

若最少删一条边

如果删的是非树边 $e$，则删的一定是唯一的一条奇边。

如果删的是树边 $e=(u,fa_u)$，显然 $S\subset T(e)$，而如果 $T(e)\neq S$，任取偶边 $e_1\in T(u)\setminus S$，奇边 $e_2\in T(u)\cap S$，$e_1,e_2$ 和若干条（偶数条）依然构成一个奇环。

综上，删一条边的情况等价于 $\exist e\ s.t. \ T(e)=S$。

若最少删两条边

设删去 $x_1,x_2$ 两条边，设 $A_i=T(x_i)\cap S,B_i=T(x_i)\setminus S,i=1,2$。

显然 $A_i,B_i$ 均非空，否则可以删一条边解决。

任取 $e_1\in A_1,e_2\in B_1$，$e_1,e_2$ 和树边构成的奇环并没有因为 $x_1$ 切断，因此 $x_2$ 一定切断了这个奇环，这也就意味着对于 $x_2$ 来说，$e_2$ 是跨过这条边的返祖边，即 $e_2\in B_2$，同时如果 $e_1\in A_2$，则这个奇环还是没有切断，因此 $e_1\not\in A_2$，即 $B_1\subset B_2,A_1\cap A_2=\emptyset$。

对 $e_1\in A_2,e_2\in B_2$ 结论同样成立，因此 $B_1=B_2$。 又显然任意 $e\in S$ 他至少在 $A_1,A_2$ 之一里，所以可以删两条边的情况等价于：

$\exist x_1,x_2$ s.t. $A_1\cup A_2=S,A_1\cap A_2=\emptyset,B_1=B_2$。

程序实现

发现维护集合是复杂度非常不合理的，可以考虑哈希，注意到我们只需要维护集合，并且需要实现集合的加减等操作，因此可以考虑异或哈希，给每条边随机权值 $h_e$，集合 $S$ 的哈希值 $hash(S)=\oplus_{e\in S}h_e$。

mt19937_64 rnd(time(0));
int head[N],ecnt;
int col[N],dep[N];
ull S,T[N];
bool vis[N];
map<ull,int> cnt;

struct Edge{
    int to,next;
}e[N<<1];

void add(int x,int y){
    e[++ecnt]=(Edge){y,head[x]},head[x]=ecnt;
}

void dfs(int u,int fa){
    vis[u]=true;
    RepG(i,u){
        int v=e[i].to;
        if(v==fa)continue;
        if(!vis[v]){
            col[v]=col[u]^1;
            dep[v]=dep[u]+1;
            dfs(v,u);
            T[u]^=T[v];
        }
        else if(dep[v]<dep[u]){
            ull x=rnd();
            T[u]^=x;
            T[v]^=x;
            if(col[u]==col[v])S^=x;
            cnt[x]++;
        }
    }
    cnt[T[u]]++;
}

long long count_ways(int n, std::vector<int> U, std::vector<int> V) {
    for(int i=0;i<U.size();i++)add(U[i],V[i]),add(V[i],U[i]);
    dfs(1,0);
    if(!S)return 1;
    else if(cnt[S])return cnt[S];
    else{
        ll res=0;
        for(auto [x,t]:cnt)res+=1ll*t*cnt[x^S];
        return res/2;
    }
}