第21天。
今天的题目是 Is Graph Bipartite? :
Given an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j
for which the edge between nodes i
and j
exists. Each node is an integer between 0
and graph.length - 1
. There are no self edges or parallel edges: graph[i]
does not contain i
, and it doesn’t contain any element twice.
1Example 1:2Input: [[1,3], [0,2], [1,3], [0,2]]3Output: true4Explanation:5The graph looks like this:60----17| |8| |93----210We can divide the vertices into two groups: {0, 2} and {1, 3}.11Example 2:12Input: [[1,2,3], [0,2], [0,1,3], [0,2]]13Output: false14Explanation:15The graph looks like this:5 collapsed lines
160----117| \ |18| \ |193----220We cannot find a way to divide the set of nodes into two independent subsets.
Note:
graph
will have length in range[1, 100]
.graph[i]
will contain integers in range[0, graph.length - 1]
.graph[i]
will not containi
or duplicate values.- The graph is undirected: if any element
j
is ingraph[i]
, theni
will be ingraph[j]
.
这是一道关于图的问题,题目的意思很简单,就是要判断一个图是不是一个二部图,所谓的二部图,就是一个图可以把所有节点划分到两个不相交的两个集合,这两个集合内部没有边相连。
我们可以对图进行一次遍历,遍历的时候对节点进行着色,着色的规律是这样的,当从一个节点跳到另一个节点的时候,我们就切换一次颜色(共有三种颜色,其中一种表示没有访问,即白色)。因为遍历完了之后,整个图的节点就被划分成两部分了,接下来我们只需要判断所有节点的邻居是否和它是不同色的即可。代码如下:
1char color;2bool isBipartite(vector<vector<int>>& graph) {3 int size = graph.size();4 vector<char> flags(size, 'w');5 // w g b6 color = 'b';7 for(int i = 0;i < size;i++) {8 if (flags[i] == 'w') {9 dfs(graph, flags, i);10 }11 }12
13 for(int i = 0;i < size;i++) {14 for(auto j: graph[i]) {15 if (flags[i] == flags[j]) return false;15 collapsed lines
16 }17 }18 return true;19}20
21void dfs(vector<vector<int>> &graph, vector<char> &flags, int index) {22 flags[index] = color;23 for(auto j: graph[index]) {24 if (flags[j] == 'w') {25 color = ~color;26 dfs(graph, flags, j);27 color = ~color;28 }29 }30}