1. 题目
给定一组 N 人（编号为 1, 2, …, N）， 我们想把每个人分进任意大小的两组。
每个人都可能不喜欢其他人，那么他们不应该属于同一组。
形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。
代码语言：javascript复制示例 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 <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/possible-bipartition 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 把人分成2组，组内没有自己不喜欢的人
2.1 DFS
着色法，初始颜色均为0，着色成1或者2，遇到矛盾的返回 false
代码语言：javascript复制class Solution {
unordered_map<int,unordered_set<int>> m;
bool ans = true;
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
if(dislikes.size() <= 2) return true;
vector<int> color(N 1, 0);
for(auto& d : dislikes)//建图
{
m[d[0]].insert(d[1]);
m[d[1]].insert(d[0]);
}
for(int i = 1; i <= N; i )
{
if(color[i] == 0)//未着色的
{
color[i] = 1;//着色为1
dfs(i, 1, color);
if(!ans)
return false;
}
}
return true;
}
void dfs(int id, int col, vector<int> &color)
{
if(!ans) return;
int nextcol = col==1 ? 2 : 1;//跟我相连的(不喜欢的人)颜色相反
for(auto it = m[id].begin(); it != m[id].end(); it )
{
if(color[*it] == col)//颜色相同，出错
ans = false;
if(color[*it] == 0)//没有访问过的，继续着色
{
color[*it] = nextcol;
dfs(*it, nextcol, color);
}
}
}
};528 ms 71.3 MB
2.2 BFS
- 思路跟dfs一样，实现形式不一样而已
class Solution {
unordered_map<int,unordered_set<int>> m;
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
if(dislikes.size() <= 2) return true;
vector<int> color(N 1, 0);
for(auto& d : dislikes)//建图
{
m[d[0]].insert(d[1]);
m[d[1]].insert(d[0]);
}
queue<int> q;
int id, col = 1, nextcol, size;
for(int i = 1; i <= N; i )
{
if(color[i] == 0)//未访问的
{
color[i] = 1;//着色为1
col = 1;
q.push(i);
while(!q.empty())
{
size = q.size();
nextcol = col==1 ? 2 : 1;//下一层颜色需要变
while(size--)
{
id = q.front();
q.pop();
for(auto it = m[id].begin(); it != m[id].end(); it )
{ //相连的，不喜欢的，颜色不能一样
if(color[*it] == col)
return false;
if(color[*it] == 0)
{
color[*it] = nextcol;//没访问的，不喜欢的，颜色跟我不一样
q.push(*it);
}
}
}
col = col==1? 2 : 1;//换颜色
}
}
}
return true;
}
};524 ms 70.9 MB
2.3 并查集
- 参考 数据结构–并查集（Disjoint-Set）
参考了题解区大佬们的思路
- 把并查集大小开到2倍的N，左边是自己的颜色，右边是自己不喜欢的另一种颜色
- 当a,b互斥时，a 与 b 对应的相反颜色 b N 应该是一致的，进行
merge(a, b N) - 同理，
merge(b, a N)
class dsu
{
vector<int> f;
public:
dsu(int n)
{
f.resize(n 1);
for(int i = 0; i < n 1; i)
f[i] = i;
}
void merge(int a, int b)
{
int fa = find(a), fb = find(b);
f[fa] = fb;
}
int find(int a)//循环 路径压缩
{
int origin = a;
while(a != f[a])
a = f[a];
return f[origin] = a;//路径压缩
}
};
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
if(dislikes.size() <= 2) return true;
dsu u(2*N 1);
int a, b, da, db;
for(auto& d : dislikes)
{
a = d[0];
b = d[1];
da = a N;//a的另外一种颜色
db = b N;//b的另外一种颜色
if(u.find(a) == u.find(b))
return false;
u.merge(a,db);//a跟b互斥，那么a跟b的反是一样的颜色
u.merge(b,da);//同理
}
return true;
}
};256 ms 39.6 MB
