题目链接：https://ac.nowcoder.com/acm/contest/7016/F
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13530156.html

题目描述

“サーヴァント、キャスター、Medea。”–紫魔法师

给出一棵仙人掌(每条边最多被包含于一个环，无自环，无重边，保证连通)，要求用最少的颜色对其顶点染色，满足每条边两个端点的颜色不同，输出最小颜色数即可

输入描述:
第一行包括两个整数n,m，表示顶点数和边数
$n<=100000,m<=200000$
接下来m行每行两个整数$u,v$，表示$u,v$之间有一条无向边，保证数据合法

输出描述:
一行一个整数表示最小颜色数

输入
3 4
1 2
2 3
3 4
1 4

输出
2

emmm,很明显，对于一棵树而言，其染色的颜色数只需要2种即可，只不过这题多了个环，那么我们画个图看看就知道了：

然后我们就大概知道了，如果环内的点数为奇数个的话，那么就必须要再多加一种颜色，所以我们只需要判断一下是否有奇环存在即可。

怎么判断呢，直接dfs即可，然后用vis标记下每个节点出现的时间，当他再次出现的时候我们计算一下和原来的差值即可。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;#define debug printf("#$#%\n")
const int mac=1e5+10;
const int mod=1e9+7;
typedef long long ll;int mk=0;
vector<int>g[mac];
int vis[mac];void dfs(int u,int fa,int nb)
{vis[u]=nb;for (auto v:g[u]){if (mk) return;if (v==fa) continue;if (!vis[v]) dfs(v,u,nb+1);else if (abs(vis[u]-vis[v])%2==0) {mk=1; return;}}
}int main(int argc, char const *argv[])
{int n,m;scanf ("%d%d",&n,&m);for (int i=1; i<=m; i++){int u,v;scanf ("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0,1);if (n==1) printf("1\n");else if (mk) printf("3\n");else printf("2\n");return 0;
}