CF19E Fairy 做题记录

给定一张 $n$ 个点 $m$ 条边的无向图，求有哪些边满足删掉这一条边后的图是二分图。

$1\le n\le 10^4$，$0\le m\le 10^4$，要求线性。

显然要求的是所有奇环的交。

考虑图的任意一棵生成树，称只包含一条返祖边的环为本源环，那么有个结论就是所有简单环都可以通过若干个本源环异或得到。

证明是显然的，每个简单环都等价于环中非树边对应的本源环异或起来。

接下来开始 Jelly Wen 定理，挖掘一条边可以成为答案的必要条件：

• 必须要被所有奇本源环覆盖，这个显然；

• 不能被任何偶本源环覆盖，这是因为删掉这条边后随便找一个奇本源环异或上覆盖它的偶本源环就可以得到一个奇环：

  

现在来证明这些必要条件的并是充要条件：

• 所有奇环都是由奇数个奇本源环异或上若干个偶本源环得到的；
• 被删掉的这条边被所有奇本源环覆盖且不被任何偶本源环覆盖；
• 所以所有奇环中，被删掉的这条边都被本源环覆盖了奇数次；
• 所以最后的图不存在奇环；

那么用树上差分维护即可，时间复杂度 $O(n)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int S=10005;

int n,m;
vector<pair<int,int>> g[S];
bool vis[S];
vector<int> son[S];
int fid[S],dep[S],col[S];
int ctt,tot[S];

void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	col[u]=col[fa]^1;
	son[fa].push_back(u);
	vis[u]=true;
	int cnt=0;
	for(auto t:g[u])
	{
		int v=t.first;
		if(!vis[v]) fid[v]=t.second,dfs(v,u);
		else if(v==fa)
		{
			if(++cnt>=2) ctt++,tot[u]--,tot[fa]++;
		}
		else if(dep[v]<dep[u])
		{
			if(col[u]==col[v]) ctt++,tot[u]++,tot[v]--;
			else tot[u]--,tot[v]++;
		}
	}
}

void dfs2(int u)
{
	vis[u]=true;
	for(int v:son[u])
	{
		dfs2(v);
		tot[u]+=tot[v];
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back({y,i}),g[y].push_back({x,i});
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
	if(ctt==0)
	{
		printf("%d\n",m);
		for(int i=1;i<=m;i++) printf("%d ",i);
		printf("\n");
		return 0;
	}
	for(int i=1;i<=n;i++) vis[i]=false;
	for(int i=1;i<=n;i++) if(!vis[i]) dfs2(i);
	vector<int> ans;
	for(int i=1;i<=n;i++) if(tot[i]==ctt&&fid[i]!=0) ans.push_back(fid[i]);
	if(ctt==1)
	{
		for(int u=1;u<=n;u++)
		{
			for(auto t:g[u])
			{
				int v=t.first;
				if(v<u&&col[u]==col[v]) ans.push_back(t.second);
			}
		}
	}
	sort(ans.begin(),ans.end());
	printf("%d\n",ans.size());
	for(int u:ans) printf("%d ",u);
	printf("\n");
	return 0;
}