题意
给定 \(n\) 个点 \(m\) 条边的无向连通图，判断是否有存在生成树满足：度数为奇数的点个数为 \(4\) 的倍数。
\(1\le n\le200000,1\le m\le400000\)
题解
度数总和是 \(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;
}