首页 > Graph Coloring I
开通博客写题解
头像 Bernard5
发表于 2020-12-01 21:25:18
本题其实考察了一个基础知识： 可以将图的结点用两种颜色染色，满足相邻点不同色的图，称为二分图。而在不满足二分图构成条件的图里，一定可以找到一个简单奇环。 在明确这一点的基础上，就可以使用dfs对图结构进行染色。在dfs的过程中，用栈保存点结构的遍历信息，从而检索出现奇数环的情况。 #includ 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 威风镰鼬
发表于 2021-08-26 21:44:36
思路 无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 苟且的狮子
发表于 2020-08-02 19:12:20
dfs 题意： 分析： 深搜没学好啊！我们会发现，这其实就是一个判断图是否是二分图的过程！那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！ 染色部分容易，广搜深搜都可以，分深度奇偶染色即可。但是，要我们找环，就有点困难了。因为要是环，所以我们选择深搜，因为要 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 (́安◞౪◟排‵)
发表于 2020-06-29 22:09:10
用dfs对图染色，如果不冲突则第一种情况输出如果冲突则退出进入奇数环判断（第二种情况）不可能两种情况都不满足 #include<bits/stdc++.h> using namespace std; struct oppo { int to,next; } rood[600005 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”