二分图的定义
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
1.如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
2.另一个比较理解的解释是: 给你一幅”图”，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，能做到吗？做到就是二分图, 做不到就不是二分图
3.电商环境下<用户, 商品>点击pair之间形成了一个 bipartite
那么如何判定一张图是二分图?
按照这种染色的定义, 我们只要能染成两类颜色那么就是二部图, 否则就不是.
所以从第一个节点开始, 我们模拟染色的过程, 给第一个节点染一个颜色, 从这个节点出发进行遍历
1.如果我们起始的节点r的下一个节点n会有两种情况: a.这个邻居节点n没有被染色, 直接染色这个邻居, 然后从这个邻居n开始遍历; b.这个邻居节点n已经被染色了, 而且颜色和r相同, 那么返回false
2.图不一定是完全联通的, 可能存在多个子图, 所以对所有的节点都要作为起点都遍历一遍, 直到发现有不满足染色条件为止
785.判断二分图
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
不存在自环（graph[u] 不包含 u）。不存在平行边（graph[u] 不包含重复值）。如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。如果图是二分图，返回 true ；否则，返回 false 。示例 1：输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false 解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
示例 2：输入：graph = [[1,3],[0,2],[1,3],[0,2]] 输出：true 解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。
分析:
1.如果我们起始的节点r的下一个节点n会有两种情况:
(i). 这个邻居节点n没有被染色, 直接染色这个邻居, 然后从这个邻居n开始遍历
(ii). 这个邻居节点n已经被染色了, 而且颜色和r相同, 那么返回 false
2.图不一定是完全联通的, 可能存在多个子图, 所以对所有的节点都要作为起点都遍历一遍, 直到发现有不满足染色条件为止
class Solution {
public:
int valid = true;
int UNCORORED = 0;
int RED = 1;
int BLUE = 2;
void dfs(int i, int curColor, vector<vector<int>>& graph, vector<int>& color) {
color[i] = curColor;
int nextColor = (curColor == RED) ? BLUE : RED;
for (int neighbor : graph[i]) {
if (color[neighbor] == UNCORORED) {
dfs(neighbor, nextColor, graph, color);
} else if (curColor == color[neighbor]) {
valid = false;
}
}
return;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n, UNCORORED);
for (int i = 0; i < n; ++i) {
if (color[i] == UNCORORED) {
dfs(i, RED, graph, color);
}
}
return valid;
}
};
886.可能的二分法
给定一组 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
class Solution {
public:
int UNCOLORED = 0;
int RED = 1;
int BLUE = 2;
bool valid = true;
void dfs(int i, int curColor, vector<vector<int>>& graph, vector<int>&color) {
color[i] = curColor;
int nextColor = (curColor == RED) ? BLUE : RED;
for (int neighbor : graph[i]) {
if (color[neighbor] == UNCOLORED) {
dfs(neighbor, nextColor, graph, color);
} else if (curColor == color[neighbor]) {
valid = false;
}
}
return;
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> graph(n+1);
for (vector<int> dis : dislikes) {
int x = dis[0];
int y = dis[1];
graph[x].push_back(y);
graph[y].push_back(x);
}
vector<int> color(n+1, UNCOLORED);
for (int i = 1; i <= n; ++i) {
if (color[i] == UNCOLORED) {
dfs(i, RED, graph, color);
}
}
return valid;
}
};
转载请注明来源, from goldandrabbit.github.io
