785.Is Graph Bipartite?¶
Tags: Medium
Depth-first Search
Breadth-first Search
Graph
Links: https://leetcode.com/problems/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.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We 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]
.
这种题的解法就是很典型的图染色问题,染色问题一般分为四色问题的染色,和二部图的染色。
用一个数组d
去记录每个节点的颜色,因为只有两种颜色,不用考虑回退,所以只需要保证直接相邻的两个节点颜色不一致即可,初始化为-1
,即未染色。对于每个未染色的节点,采用DFS进行深搜即可。
class Solution {
int n;
public:
bool isBipartite(vector<vector<int>>& graph) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
n = graph.size();
vector<int> d(n, -1);
for (int i = 0; i < n; ++i) {
if (d[i] == -1) {
if (!DFS(i, 0, d, graph)) return false;
}
}
return true;
}
bool DFS(int pos, int color, vector<int> & d, vector<vector<int>> & graph)
{
d[pos] = color ^ 1; //只需要用01染色
for (int i = 0; i < graph[pos].size(); ++i) {
if (d[graph[pos][i]] == -1) {
if (!DFS(graph[pos][i], d[pos], d, graph)) return false;
}
else if (d[graph[pos][i]] != color) return false;
}
return true;
}
};