二分图判断
例如这就是一个二分图。 大概就是把顶点分成两堆，每堆内部没有边。
无向图G为二分图的充分必要条件是，G至少有两个顶点, 且其所有回路的长度均为偶数。
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B)，则称图G为一个二分图。
二分图的另一种等价的说法是，可以把每个节点着以黑色和白色之一，使得每条边的两个端点颜色不同.不难发现，非连通的图是二分图当且仅当每个连通分量都是二分图，因此我们只考虑无向连通图。
判断二分图的常见方法：开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，用深搜即可。
详细步骤
- 初始化染色数组。染色数组包含三种状态：未染色（-1），0，1。
- 每一个节点深度遍历。若该节点未染色则进行染色，递归地对相邻节点进行染色，当发现相邻节点染色与当前节点相同，返回false
class Solution {
public:
bool dfs(vector<vector<int>>& graph,vector<int> &colors,int i){
int color = colors[i]==-1?0:colors[i];
// if(colors[i]==-1)
auto adjs = graph[i];
colors[i]=color;
bool ans;
for(auto j=0;j<adjs.size();j++){
if(colors[adjs[j]]==color) return false;
else if(colors[adjs[j]]==-1) {
colors[adjs[j]]=1-color;
if(!dfs(graph,colors,adjs[j])) return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n=graph.size();
vector<int> colors (n,-1);
for(auto i=0;i<n;i++){
if(!dfs(graph,colors,i)) return false;
}
return true;
}
};
python
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
ans = True
color = collections.defaultdict(int)
n = len(graph)
def dfs(i):
nonlocal ans
if not ans:
return
if color[i] == 0:
color[i] = 1
cur = color[i]
for neighbor in graph[i]:
if color[neighbor] == cur:
ans = False
break
if color[neighbor] == 0:
color[neighbor] = 2 if cur == 1 else 1
dfs(neighbor)
for i in range(n):
if color[i] == 0:
dfs(i)
# print(color)
return ans