SEERC2022 D Divisible by 4 Spanning Tree 题解

题意

给定 (n) 个点 (m) 条边的无向连通图，判断是否有存在生成树满足：度数为奇数的点个数为 (4) 的倍数。

(1le nle200000,1le mle400000)

题解

度数总和是 (2n-2)，所以度数为奇数的点个数一定是偶数。

随便找一个生成树，如果满足条件就做完了。

否则需要判断奇数点个数模 (4) 能否发生变化。

这个限制看起来不是很紧，所以考虑大力讨论。

首先图上所有的桥是必选的，此时每个点度数已经有值了。

每个双连通分量是独立的，只要有一个能改变模 (4) 的值即可。

环

如果有连续的三个点 (x,y,z) 满足 (x,z) 奇偶不同则有解：

选择环上一条边断开等价于选择这条边上两点改变奇偶。

不妨令 (x,y) 奇偶相同，则 (y,z) 奇偶不同，贡献可以自由选择是 (0) 或 (2)。

两个环恰有一个交点

则两个环大小均不小于 (3)，可以使用一个环选择是否改变公共点的奇偶，剩下的环贡献就是自由的。

此时一定有解。

两个环交于路径 ((u,v))

此时 (u,v) 之间恰好有三条路径，删边要求的是每条路径恰好删一条。

• 当一条路径长度大于等于 (3)：

这条路径上可以选中里面的边（和其它路径的点不交）或 (u) 作为端点的边，(u) 的奇偶是自由的。

于是剩下两条路径组成长度至少为 (4) 的环可以保证有解。

• 路径长度为 ((2,1,2))

讨论发现可以改变任意两点奇偶，有解。

• 路径长度为 ((2,2,2))

讨论打表发现仅有以下情况无解：

图可以表示成 ((1,2),(1,3),(1,4),(2,5),(3,4),(4,5)) ，且 (2,3,4) 奇偶相同，(1,5) 奇偶不同。

其它情况

显然包含合法子图，有解。

结论

当任意生成的生成树合法或所有双连通分量都不满足：

• 是一个环且满足任意距离为 (2) 的点奇偶相同

• 不是上文中 (5) 个点 (6) 条边的特定图

时有解。

时间复杂度：(O(n+m))。

代码：

#include <bits/stdc++.h>
using namespace std;
bool solve(){
	int n,m,tot=0,k=0;
	scanf("%d%d",&n,&m);
	vector<int> st,dfn(n),low(n),bel(n),b(n),d(n);
	vector<vector<int>> e(n),p(n),g(n);
	for(int u,v;m--;)
		scanf("%d%d",&u,&v),u--,v--,e[u].push_back(v),e[v].push_back(u);
	auto dfs=[&](auto self,int x,int fa)->void{
		st.push_back(x);
		int&l=low[x];
		dfn[x]=l=++tot;
		for(int y:e[x])
			if(!dfn[y]){
				b[x]^=1;b[y]^=1;
				self(self,y,x);l=min(l,low[y]);
				if(low[y]>dfn[x]) d[x]^=1,d[y]^=1;
			}else if(y!=fa) l=min(l,dfn[y]);
		if(dfn[x]!=l) return;
		while(st.back()!=x) p[bel[st.back()]=k].push_back(st.back()),st.pop_back();
		p[bel[x]=k++].push_back(x);
		st.pop_back();
	};
	dfs(dfs,0,-1);
	if(accumulate(b.begin(),b.end(),0)%4==0) return 1;
	for(int x=0;x<n;x++) for(int y:e[x]) if(bel[x]==bel[y]) g[x].push_back(y);
	auto chk=[&](int id){
		int sz=p[id].size(),cnt=0;
		for(int x:p[id]) cnt+=g[x].size();
		cnt/=2;
		if(cnt<sz) return 0;
		if(cnt>sz&&!(cnt==6&&sz==5)) return 1;
		if(cnt==sz){
			for(int i=0;i<sz;i++) if(d[p[id][i]]^d[p[id][(i+2)%sz]]) return 1;
			return 0;
		}
		auto ok=[&](int x,int y){
			if(g[x].size()!=3||g[y].size()!=3||d[x]==d[y]||
			find(g[x].begin(),g[x].end(),y)!=g[x].end())
				return 0;
			int c=-1;
			for(int u:p[id]) if(u!=x&&u!=y){
				if(~c&&c!=d[u]) return 0;
				c=d[u];
			}
			return 1;
		};
		for(int i=0;i<sz;i++) for(int j=i+1;j<sz;j++) if(ok(p[id][i],p[id][j])) return 0;
		return 1;
	};
	for(int id=0;id<k;id++) if(chk(id)) return 1;
	return 0;
}
int main(){
	int t;scanf("%d",&t);
	while(t--) puts(solve()?"YES":"NO");
	return 0;
}