本文涉及的点
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}
代码
class Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> 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);
}
vector<int> group(n, -1);
vector<int> vis(n);
auto Add = [&](queue<int>& que, int cur) {
if (vis[cur]) { return; }
que.emplace(cur);
vis[cur] = true;
};
auto BFS = [&](int root) {
if (vis[root]) { return true; }
queue<int> 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;
vector<vector<int>> 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);
}
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
