[bzoj5295]染色

 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\n");
71         else printf("YES\n");
72     }
73 }