AlgoPressAppearance
0886-可能的二分法
https://leetcode.cn/problems/possible-bipartition
给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。 每个人都可能不喜欢其他人，那么他们不应该属于同一组。 形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。 当可以用这种方法将所有人分进两组时，返回 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 <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j
思路：模拟法【未实现】
从第一个元素开始按照 dislikes 分到两个组 依次遍历 dislikes ，将下面的继续分组
csharp
public class Solution {
private List<int> part0;
private List<int> part1;
private bool part(int index, int[][] dislikes){
int num0 = dislikes[index][0];
int num1 = dislikes[index][1];
if(num0 == num1 && num1 == 0){
return true;
}
if(part0.Contains(num0)){
if(part0.Contains(num1)){
return false;
}
else{
if(!part1.Contains(num1)){
part1.Add(num1);
}
return true;
}
}
else if(part0.Contains(num1)){
if(part0.Contains(num0)){
return false;
}
else{
if(!part0.Contains(num1)){
part0.Add(num1);
}
}
}
return true;
}
public bool PossibleBipartition(int n, int[][] dislikes) {
part0 = new List<int>();
part1 = new List<int>();
bool result = true;
for(int i=0; i<dislikes.Length; i++){
result = result && part(0,dislikes);
}
return result;
}
}
思路：着色
将任一结点涂成红色，然后将它的所有邻居都涂成蓝色，然后将所有的邻居的邻居都涂成红色，以此类推。 如果我们将一个红色结点涂成蓝色（或蓝色结点涂成红色），那么就会产生冲突。
实现方式： 使用两个字典，第一个字典记录每个人 dislike 的人的清单 第二个字典记录涂色(分组)记录，从第一个人开始涂色，然后递归涂色邻居，在涂色邻居的邻居，直到循环结束
参考代码
csharp
public class Solution {
Dictionary<int,List<int>> graph;
Dictionary<int,int> color;
public bool PossibleBipartition(int n, int[][] dislikes) {
graph = new Dictionary<int,List<int>>();
for(int i=1; i<=n; i++){
List<int> list = new List<int>();
graph.Add(i,list);
}
//设置 dislikes 清单存到图中
for(int i=0; i<dislikes.Length; i++){
graph[dislikes[i][0]].Add(dislikes[i][1]);
graph[dislikes[i][1]].Add(dislikes[i][0]);
}
//着色（使用字典储存涂色信息，0表示红色，1表示蓝色）
color = new Dictionary<int,int>();
for(int node = 1; node <= n; node++){
//如果这个节点没有涂色，且也不能涂成对应颜色，则失败
//从第一个节点开始 涂红色，然后dfs递归涂对方颜色
if(!color.ContainsKey(node) && !dfs(node,0)){
return false;
}
}
return true;
}
private bool dfs(int node, int c){
//如果目标已经涂色且和需要涂的颜色对应，则直接返回true，否则返回false
if(color.ContainsKey(node)){
return color[node] == c;
}
//开始涂色
color.Add(node,c);
//将不喜欢列表的所有人涂成对方颜色 c ^ 1
for(int i=0; i<graph[node].Count; i++){
if(!dfs(graph[node][i] , c ^ 1))
{
return false;
}
}
return true;
}
}