一、二分图判定
1.1 二分图概念及应用
1.概念
二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。
给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？
这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：
能够染色的充要条件：
二分图当且仅当图中不含有奇数环
2.为什么使用二分图，有何优势？
从简单实用的角度来看，二分图结构在某些场景可以更高效地存储数据。
比如说我们需要一种数据结构来储存电影和演员之间的关系：某一部电影肯定是由多位演员出演的，且某一位演员可能会出演多部电影。你使用什么数据结构来存储这种关系呢？
既然是存储映射关系，最简单的不就是使用哈希表嘛，我们可以使用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射，如果给一部电影的名字，就能快速得到出演该电影的演员。
但是如果给出一个演员的名字，我们想快速得到该演员演出的所有电影，怎么办呢？这就需要「反向索引」，对之前的哈希表进行一些操作，新建另一个哈希表，把演员作为键，把电影列表作为值。
显然，二分图相较于哈希表的优势：
如果用哈希表存储，需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图
1.2 染色法-二分图判定
1.二分判定基础题
说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。
既然说到遍历图，也不涉及最短路径之类的，当然是 DFS 算法和 BFS 皆可了，DFS 算法相对更常用些，所以我们先来看看如何用 DFS 算法判定双色图。
我们借由图遍历框架，能够写出给二分图作色的代码:
void dfs(vector<vector<int>>& graph,int now){
visited[now] = true;
for(int s : graph[now]){
if(!visited[s]){
color[s] =!color[now];
dfs(graph,s);
}
} 同时如果再遍历一次判断color[s]==color[now]（不需要进行去重，只要有邻居和now不匹配就是非二分）
为了代码的简洁性，将二者写在一起，有如下代码：
class Solution {
public:
bool jud =false;
vector<bool> color;
vector<bool> visited;
void dfs(vector<vector<int>>& graph,int now){
visited[now] = true;
for(int s : graph[now]){
if(!visited[s]){
color[s] =!color[now];
dfs(graph,s);
}
else{
if(color[s]==color[now]){
jud = true;
return;
}
}
}
}
bool isBipartite(vector<vector<int>>& graph) {
int num = graph.size();
visited = vector<bool>(num,false);
color = vector<bool>(num,false);
for(int i =0;i < num;i++)
dfs(graph,i);
return !jud;
}
};2.可能的二分-延申
此题也是一个二分图问题，n个人分为两组就是将n个点染色为两种，然后dislikes数组表示不能同色的人，其实在二分图中就是相连接的节点就是数组中的组合，因为相邻节点和dislike中组合都不能同色。
1：无向图的构建
2：使用引用传值会比直接值传递快很多（不用&传递会超时）
3：最后for循环时用visited可以排除已经染色的点，提升一点效率
那么，根据二分图判定，有以下代码：
class Solution {
public:
vector<bool> visited;
vector<bool> color;
bool jud = true;
vector<vector<int>> buildgraph(int n,vector<vector<int>>& dislikes){
vector<vector<int>> graph(n+1);
for(auto s : dislikes){
int one = s[0],two = s[1];
graph[one].push_back(two);
graph[two].push_back(one);
}
return graph;
}
void dfs(vector<vector<int>>& graph,int now){
if (!jud) return;
visited[now] = true;
for(auto s : graph[now]){
if(!visited[s]){
color[s] = !color[now];
dfs(graph,s);
}else{
if(color[now]==color[s]){
jud = false;
return;
}
}
}
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
visited = vector<bool>(n+1,false);
color = vector<bool>(n+1,false);
// color.resize(n + 1);
// visited.resize(n + 1);
vector<vector<int>> graph = buildgraph(n,dislikes);
for(int i = 1;i <= n;i++)
if (!visited[i]){
dfs(graph,i);
}
return jud;
}
};
