合肥市门窗工程在哪个网站接活做,品牌活动策划方案,结构设计师之家官网,做网站霸屏公司销售好做吗本文涉及的点
CBFS算法
LeetCod886. 可能的二分法
给定一组 n 人#xff08;编号为 1, 2, …, n#xff09;#xff0c; 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人#xff0c;那么他们不应该属于同一组。 给定整数 n 和数组 dislikes #xff0c;其…本文涉及的点
CBFS算法
LeetCod886. 可能的二分法
给定一组 n 人编号为 1, 2, …, n 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人那么他们不应该属于同一组。 给定整数 n 和数组 dislikes 其中 dislikes[i] [ai, bi] 表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时返回 true否则返回 false。 示例 1 输入n 4, dislikes [[1,2],[1,3],[2,4]] 输出true 解释group1 [1,4], group2 [2,3] 示例 2
输入n 3, dislikes [[1,2],[1,3],[2,3]] 输出false 示例 3
输入n 5, dislikes [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出false
提示 1 n 2000 0 dislikes.length 104 dislikes[i].length 2 1 dislikes[i][j] n ai bi dislikes 中每一组都 不同
二分图
本题本质是最简单的二分图如果有模板可用染色法解决。
CBFS
不失一般性我们设1号在第0组。 BFS状态leves[0]{1},leves[i]记录leves[i-1]的讨厌的人。空间复杂度O(n) BFS后续状态枚举cur讨厌的人next如果next已经有分组且和cur的分组相同返回false。否则将next分配到和cur不同的分组。时间复杂度O(m)m是边数。 BFS的初始状态1在0分组。 BFS的返回值枚举结束返回true。 BFS的出重处理不需要。每个延误都要处理。 group[i] 为0在第0组为1在第1组-1未分组。可能有多个连通区域故没处理的节点都要BFS一次。 注意是无向图节点从1开始可转化成从0开始。 以下想法是错误的 将无向图转成有向图编号小的指向遍好大的。{1,3},{2,3}
代码
class Solution {public:bool possibleBipartition(int n, vectorvectorint dislikes) {vectorvectorint vNeiBo(n);for (const auto v : dislikes) {vNeiBo[v[0]-1].emplace_back(v[1] - 1);vNeiBo[v[1] - 1].emplace_back(v[0] - 1);}vectorint group(n, -1);vectorint vis(n);auto Add [](queueint que, int cur) {if (vis[cur]) { return; }que.emplace(cur);vis[cur] true;};auto BFS [](int root) {if (vis[root]) { return true; }queueint que;Add(que, root);group[root] 0;while (que.size()) {const auto cur que.front();que.pop();for (const auto next : vNeiBo[cur]) {if (group[next] group[cur]) {return false; }group[next] (group[cur] 1) % 2;Add(que, next);}}return true;};for (int i 0; i n; i) {if (!BFS(i)) { return false; }}return true;}};测试用例 int n;vectorvectorint dislikes;TEST_METHOD(TestMethod1){n 4, dislikes { {1,2},{1,3},{2,4} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(true, res);}TEST_METHOD(TestMethod2){n 3, dislikes { {1,2},{1,3},{2,3} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(false, res);}TEST_METHOD(TestMethod3){n 5, dislikes { {1,2},{2,3},{3,4},{4,5},{1,5} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(false, res);}TEST_METHOD(TestMethod4){n 2, dislikes { {1,2} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(true, res);}TEST_METHOD(TestMethod5){//无向图n 2, dislikes { {2,1} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(true, res);}TEST_METHOD(TestMethod13){n 50, dislikes { {39,46},{4,41},{3,35},{8,44},{22,44},{7,49},{28,41},{7,25},{6,35},{2,22},{34,35},{3,7},{1,11},{11,48},{8,24},{6,7},{38,40},{37,48},{3,45},{44,45},{4,46},{23,35},{28,46},{7,28},{35,36},{18,20},{8,15},{17,41},{13,35},{6,22},{22,48},{22,39},{4,35},{8,38},{23,41},{10,41},{6,41},{18,48},{16,41},{37,44},{8,12},{18,36},{16,18},{7,44},{3,18},{10,46},{20,37},{2,37},{11,49},{30,45},{28,37},{23,37},{22,23},{5,37},{29,40},{16,35},{22,26},{46,49},{18,26},{8,9},{24,46},{8,28},{11,29},{22,24},{7,15},{4,37},{9,40},{8,32},{23,40},{40,42},{33,40},{17,45},{40,48},{12,41},{43,45},{38,41},{45,47},{12,18},{7,31},{34,37},{8,48},{4,11},{46,48},{2,7},{17,40},{12,46},{22,49},{46,50},{37,50},{22,36},{22,43},{41,44},{13,22},{11,16},{7,47},{14,37},{37,43},{13,37},{26,40},{19,41},{46,47},{16,22},{19,22},{22,33},{11,19},{35,44},{7,33},{41,49},{38,45},{25,35},{3,37},{15,22},{6,18},{11,30},{5,41},{8,33},{1,46},{31,46},{41,42},{18,28},{15,41},{35,49},{25,41},{20,45},{26,46},{8,43},{5,45},{28,40},{1,18},{23,46},{13,18},{35,38},{8,49},{11,44},{18,33},{4,7},{5,7},{10,11},{37,49},{9,22},{4,45},{32,45},{32,37},{29,35},{26,35},{7,29},{1,37},{8,14},{5,11},{18,29},{18,49},{21,41},{17,35},{7,10},{22,38},{40,43},{5,35},{33,35},{6,40},{34,40},{22,34},{16,40},{19,46},{18,39},{24,35},{19,35},{18,50},{8,17},{11,12},{27,35},{8,47},{7,9},{7,36},{8,34},{7,26},{31,41},{29,41},{10,45},{9,35},{33,46},{11,32},{34,45},{42,46},{15,40},{40,50},{30,40},{25,40},{15,37} };auto res Solution().possibleBipartition(n, dislikes);AssertEx(true, res);}如果有不明白的请加文末QQ群。如果要打包下载源码CSDN下载频道偶尔审核不通过原因未知也请加QQ群。
扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等
课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
