无向图点着色最优问题

题目：

链接：https://ac.nowcoder.com/acm/contest/215/B
来源：牛客网
给出一棵仙人掌(每条边最多被包含于一个环，无自环，无重边，保证连通)，要求用最少的颜色对其顶点染色，满足每条边两个端点的颜色不同，输出最小颜色数即可

分析：

做了这题我才发现一个无向连通图均可以在3种颜色内实现各点着色，并且当且仅当只有一个点的时候需要一种颜色，多个点的时候通过dfs和标记各点颜色情况来判断是否需要三种颜色。

代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<stack>
 6 #include<vector>
 7 #include<algorithm>
 8 #define  ll long long
 9 using namespace std;
10 const int maxn=5e5+7;
11 int top,first[maxn],flag[maxn],flag1=0;
12 struct v
13 {
14     int to,next,val;
15 }edge[maxn*4];
16 void init()
17 {
18     for(int i=0;i<maxn;i++)
19     {
20         first[i]=-1;
21     }
22     top=0;
23 }
24 void edge_(int to,int go)
25 {
26     edge[top].to=go;
27     edge[top].next=first[to];
28     first[to]=top++;
29 }
30 int dfs(int x)
31 {
32     for(int i=first[x];~i;i=edge[i].next)
33     {
34         int to=edge[i].to;
35         if(!flag[to])
36         {
37             flag[to]=3-flag[x];
38             if(!dfs(to))
39                 return 0;
40         }
41         else
42         {
43             if(flag[to]==flag[x])///判断是否需要第三种颜色
44             {
45                 return 0;
46             }
47         }
48     }
49     return 1;
50 }
51 int main()
52 {
53     init();
54     int n,m;
55     scanf("%d%d",&n,&m);
56     for(int i=1;i<=m;i++)
57     {
58         int a,b;
59         scanf("%d%d",&a,&b);
60         edge_(a,b);
61         edge_(b,a);
62     }
63     if(n==1)
64         puts("1");
65     else
66     {
67         for(int i=1;i<=n;i++)
68         {
69             if(!flag[i])
70             {
71                 flag[i]=1;
72                 if(!dfs(i))
73                 {
74                     puts("3");
75                     return 0;
76                 }
77             }
78         }
79         puts("2");
80     }
81     return 0;
82 }