[leetcode]785. Is Graph Bipartite?
[leetcode]785. Is Graph Bipartite?
Analysis
出太阳啦~—— [每天刷题并不难0.0]
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.
Explanation:
判断给定的图是否是二分图,用染色法解决
Implement
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n, 0);
for(int i=0; i<n; i++){
if(color[i] == 0){
if(!dfs(graph, color, i, 1))
return false;
}
}
return true;
}
bool dfs(vector<vector<int>>& graph, vector<int>& color, int node, int c){
color[node] = c;
for(int i=0; i<graph[node].size(); i++){
if(color[graph[node][i]] == c)
return false;
if(color[graph[node][i]] == 0 && !dfs(graph, color, graph[node][i], -c))
return false;
}
return true;
}
};