[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,l2\ge 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\n");

71         else printf("YES\n");

72     }

73 }

巴特西

[bzoj5295]染色

最新文章

热门文章