显然每一个连通块独立,不妨假设原图连通,并建立dfs树
假设树上有$k$条返祖边,并记其覆盖的点集分别为$V_{1},V_{2},...,V_{k}$
显然有奇环时无解,因此不妨假设$\forall 1\le i\le k,|V_{i}|\equiv 0(mod\ 2)$,进而$|V_{i}|\ge 4$
结论:恒有解$\iff \forall 1\le i<j\le k,V_{i}$和$V_{j}$满足以下条件之一:
必要性:考虑对$V_{i}\cap V_{j}$的情况分类讨论——
1. 若$V_{i}\cap V_{j}=\empty$,考虑两者树上最近点对,即得到两个环间一条路径的结构
将$V_{i}$和$V_{j}$均设为$\{A,B\},\{B,C\},\{C,D\},...,\{*,B\}$的形式,即可该路径两端点均选$A$
在此基础上,用$\{A,B\},\{B,C\},\{C,D\},...,\{*,A\}$形式连接路径,即无解
2. 若$|V_{i}\cap V_{j}|=1$,类似前者的做法,让两个简单环分别强制该公共点选$A$和$B$即可
3. 若$|V_{i}\cap V_{j}|\ge 2$,将两者交的端点提出,即得到两点间三条路径的结构
若其中有两条路径长度$\ge 3$,则将另一条路径均染成$\{A,B\}$,其余两条路径按$A,B$对称
具体形式仍类似前者,仅需注意结束时的$A/B$需取决于$\{A,B\}$路径长度奇偶性
若某条路径长度$=1$,由于奇环,其余两条路径长度至少为$3$,即为前者的情况
在此基础上,对两个环所对应的两条路径分类讨论,即必然为条件所述的形式
充分性:事实上,当满足结论的条件时,必然有$k\le 2$
关于这一点,考虑固定其中祖先最浅的返祖边$i$,并对其分类讨论:
1. 若$|V_{i}|=4$,则其余返祖边必然是从$V_{i}$中次浅点到$V_{i}$中最深点的子树内(除该点外)
2. 若$|V_{i}|>4$,则其余返祖边必然是从$V_{i}$中次浅点/倒数第三深点到$V_{i}$中最深点的某儿子显然不论哪种情况,对应的返祖边内部两两不满足条件,因此至多存在一条
在此基础上,不断删去图中度数$\le 1$的点,最终形式即两点间三条路径且存在两条路径长度$=2$
关于这种形式,称另一条的路径为长链,并分类讨论:
1. 若长链上所有点颜色集合均相同,显然其长度为偶数,此时链端点颜色相同,必然有解
2. 若长链上所有点颜色集合不全相同,找到第一个不同的位置,其仅能限制左端点某种颜色时的右端点
换言之,左右端点间至少有三种颜色配对方式,不妨假设分别为$AC,AD$和$BD$(颜色相同更优)
考虑其余路径上两点,必然分别为$AC$和$AD$(否则选$A$并顺次选择即可),进而选$BDAA$即可
综上,即得证
时间复杂度为$o(n+m)$,可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 10005 4 int t,n,m,x,y,flag,dfn[N],fa[N],dep[N]; 5 vector<int>e[N];vector<pair<int,int> >v; 6 void dfs(int k,int f,int s){ 7 dfn[k]=++dfn[0],fa[k]=f,dep[k]=s; 8 for(int i:e[k]) 9 if (i!=f){ 10 if (!dfn[i])dfs(i,k,s+1); 11 else{ 12 if (dfn[i]<dfn[k]){ 13 v.push_back(make_pair(i,k)); 14 if (dep[k]-dep[i]+1&1)flag=1; 15 } 16 } 17 } 18 } 19 int main(){ 20 scanf("%d",&t); 21 while (t--){ 22 scanf("%d%d",&n,&m),flag=0; 23 for(int i=1;i<=n;i++)e[i].clear(); 24 for(int i=1;i<=m;i++){ 25 scanf("%d%d",&x,&y); 26 e[x].push_back(y),e[y].push_back(x); 27 } 28 memset(dfn,0,sizeof(dfn)); 29 for(int i=1;i<=n;i++) 30 if (!dfn[i]){ 31 v.clear(),dfs(i,0,1),flag|=(v.size()>2); 32 if (v.size()==2){ 33 int cnt=0; 34 for(int j=v[0].second;j!=v[0].first;j=fa[j])dfn[j]=-1; 35 dfn[v[0].first]=-1; 36 for(int j=v[1].second;j!=v[1].first;j=fa[j])cnt+=(dfn[j]<0); 37 cnt+=(dfn[v[1].first]<0); 38 int s0=dep[v[0].second]-dep[v[0].first]+1; 39 int s1=dep[v[1].second]-dep[v[1].first]+1; 40 if ((s0==s1)&&(s0==cnt+1)||((s0==4)||(s1==4))&&(cnt==3));else flag=1; 41 } 42 if (flag)continue; 43 } 44 if (flag)printf("NO\n"); 45 else printf("YES\n"); 46 } 47 return 0; 48 }View Code