本文涉及的点
C++BFS算法
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 中每一组都 不同
二分图
本题本质是最简单的二分图，如果有模板，可用染色法解决。
C++BFS
不失一般性，我们设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}
代码
classSolution{public:boolpossibleBipartition(intn,vector<vector<int>>&dislikes){vector<vector<int>>vNeiBo(n);for(constauto&v:dislikes){vNeiBo[v[0]-1].emplace_back(v[1]-1);vNeiBo[v[1]-1].emplace_back(v[0]-1);}vector<int>group(n,-1);vector<int>vis(n);autoAdd=[&](queue<int>&que,intcur){if(vis[cur]){return;}que.emplace(cur);vis[cur]=true;};autoBFS=[&](introot){if(vis[root]){returntrue;}queue<int>que;Add(que,root);group[root]=0;while(que.size()){constautocur=que.front();que.pop();for(constauto&next:vNeiBo[cur]){if(group[next]==group[cur]){returnfalse;}group[next]=(group[cur]+1)%2;Add(que,next);}}returntrue;};for(inti=0;i<n;i++){if(!BFS(i)){returnfalse;}}returntrue;}};测试用例
intn;vector<vector<int>>dislikes;TEST_METHOD(TestMethod1){n=4,dislikes={{1,2},{1,3},{2,4}};autores=Solution().possibleBipartition(n,dislikes);AssertEx(true,res);}TEST_METHOD(TestMethod2){n=3,dislikes={{1,2},{1,3},{2,3}};autores=Solution().possibleBipartition(n,dislikes);AssertEx(false,res);}TEST_METHOD(TestMethod3){n=5,dislikes={{1,2},{2,3},{3,4},{4,5},{1,5}};autores=Solution().possibleBipartition(n,dislikes);AssertEx(false,res);}TEST_METHOD(TestMethod4){n=2,dislikes={{1,2}};autores=Solution().possibleBipartition(n,dislikes);AssertEx(true,res);}TEST_METHOD(TestMethod5){//无向图n=2,dislikes={{2,1}};autores=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}};autores=Solution().possibleBipartition(n,dislikes);AssertEx(true,res);}扩展阅读
| 我想对大家说的话 |
|---|
| 亲士工具箱：支持AutoCad2013及以上 |
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019C++17
或者 操作系统：win10 开发环境： VS2022C++17
如无特殊说明，本算法用**C++**实现。
