[bzoj5295]染色

将这张图化简，不断删掉度为1的点（类似于拓扑排序），构成了一张由环组成的图
考虑一个连通块中，设点数为n，边数为m（已经删掉了度为1的点），那么一共只有三种情况：
1.一个环($n=m$)，一定为YES
2.多个环嵌套($n+1<m$)，一定为NO
3.两个环($n+1=m$)，其实可以看成有两个点（可以重合），然后这两个点中间有三条路径，记长度分别为l1,l2,l3，那么有结论：当且仅当三条边依次为2,2和偶数时成立
证明：
首先三条边必然要同奇偶，否则存在奇环，对于奇环上的点都选择集合${AB}$即可卡掉
然后如果三条边都是奇数，由于原图不存在重边，因此最多只有一条路径上没有点，不妨设$l1,l2>1$，可以用l3来构造两点不同，l1来构造不能选AB，l2来构造不能选BA
那么三条边都是偶数，如果其中只有1条边小于等于2，那么$l1,l2ge 4$，同理可以用l3来构造两点相同，l1来卡掉都选A，l2来卡掉都选B
当有两条路径长度小于等于2（由于没有重边，所以一定都恰好为2），很容易发现无法卡掉

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 10005
 4 queue<int>q;
 5 vector<int>v[N];
 6 int t,n,m,x,y,a[N],r[N],vis[N];
 7 void dfs(int k,int fa){
 8     if (vis[k])return;
 9     vis[k]=1;
10     if (r[k]>2)a[++a[0]]=k;
11     x++;
12     for(int i=0;i<v[k].size();i++)
13         if ((r[v[k][i]]>1)&&(v[k][i]!=fa)){
14             if ((fa)||(!vis[v[k][i]]))y++;
15             dfs(v[k][i],k);
16         }
17 }
18 void calc(int k,int fa,int x,int s){
19     if (k==x){
20         a[++a[0]]=s;
21         return;
22     }
23     for(int i=0;i<v[k].size();i++)
24         if ((r[v[k][i]]>1)&&(v[k][i]!=fa))calc(v[k][i],k,x,s+1);
25 }
26 int main(){
27     scanf("%d",&t);
28     while (t--){
29         scanf("%d%d",&n,&m);
30         memset(r,0,sizeof(r));
31         memset(vis,0,sizeof(vis));
32         for(int i=1;i<=n;i++)v[i].clear();
33         for(int i=1;i<=m;i++){
34             scanf("%d%d",&x,&y);
35             r[x]++;
36             r[y]++;
37             v[x].push_back(y);
38             v[y].push_back(x);
39         }
40         for(int i=1;i<=n;i++){
41             if (!r[i])vis[i]=1;
42             if (r[i]==1)q.push(i);
43         }
44         while (!q.empty()){
45             int k=q.front();
46             q.pop();
47             vis[k]=1;
48             for(int i=0;i<v[k].size();i++)
49                 if (--r[v[k][i]]==1)q.push(v[k][i]);
50         }
51         bool flag=0;
52         for(int i=1;i<=n;i++){
53             x=y=a[0]=0;
54             dfs(i,0);
55             if ((x==y)&&(x%2==0))continue;
56             if ((a[0]<2)||(x+1<y)||(x==y)&&(x&1)){
57                 flag=1;
58                 break;
59             }
60             x=a[1];
61             y=a[2];
62             a[0]=0;
63             calc(x,0,y,0);
64             sort(a+1,a+a[0]+1);
65             if ((a[1]&1)||(a[2]&1)||(a[3]&1)||(a[2]>2)){
66                 flag=1;
67                 break;
68             }
69         }
70         if (flag)printf("NO
");
71         else printf("YES
");
72     }
73 }

View Code