题目链接：https://ac.nowcoder.com/acm/contest/7016/F
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13530156.html
题目描述 “サーヴァント、キャスター、Medea。”–紫魔法师
给出一棵仙人掌(每条边最多被包含于一个环，无自环，无重边，保证连通)，要求用最少的颜色对其顶点染色，满足每条边两个端点的颜色不同，输出最小颜色数即可
输入描述:
第一行包括两个整数n,m，表示顶点数和边数
n < = 100000 , m < = 200000 n <= 100000, m <= 200000 n<=100000,m<=200000
接下来m行每行两个整数 u , v u,v u,v，表示 u , v u,v u,v之间有一条无向边，保证数据合法
输出描述:
一行一个整数表示最小颜色数
输入
3 4
1 2
2 3
3 4
1 4
输出
2
emmm,很明显，对于一棵树而言，其染色的颜色数只需要2种即可，只不过这题多了个环，那么我们画个图看看就知道了：
文章图片
然后我们就大概知道了，如果环内的点数为奇数个的话，那么就必须要再多加一种颜色，所以我们只需要判断一下是否有奇环存在即可。
【牛客|牛客-紫魔法师（仙人掌染色-判奇环）】怎么判断呢，直接dfs即可，然后用vis标记下每个节点出现的时间，当他再次出现的时候我们计算一下和原来的差值即可。
以下是AC代码：
#include
using namespace std;
#define debug printf("#$#%\n")
const int mac=1e5+10;
const int mod=1e9+7;
typedef long long ll;
int mk=0;
vectorg[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;
}
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 求桥，边双连通缩点
- 前后缀和|牛客小白月赛5 I.区间 (interval)
- 牛客多校第一场 A-Equivalent Prefixes
- 玩一玩|超立方体及其可视化（Processing）
- 牛客|牛客练习赛3
- #|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化
- 图论|POJ1364 King 差分约束
- 图论|tarjan算法之——割点和桥
- Codeforces 1076D Edge Deletion——最短路+dfs