Description
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 contain i or duplicate values.
- The graph is undirected: if any element j is in graph[i], then i will be in graph[j].
分析
題目的意思是:判斷一個無向圖是否是一個二分圖。
- 我們采用一種很機智的染色法,大體上的思路是要将相連的兩個頂點染成不同的顔色,一旦在染的過程中發現有相連的兩個頂點已經被染成相同的顔色,說明不是二分圖。
代碼
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
vector<int> colors(graph.size());
for(int i=0;i<graph.size();i++){
if(colors[i]==0&&!isValid(graph,i,1,colors)){
return false;
}
}
return true;
}
bool isValid(vector<vector<int>>& graph,int cur,int color,vector<int>& colors){
if(colors[cur]!=0) return colors[cur]==color;
colors[cur]=color;
for(int i:graph[cur]){
if(!isValid(graph,i,-1*color,colors)){
return false;
}
}
return true;
}
};
代碼二 (python)
class Solution:
def isValid(self,graph,pos):
for i in graph[pos]:
if(i in self.colors):
if(self.colors[i]==self.colors[pos]):
return False
else:
self.colors[i]=1-self.colors[pos]
if(not self.isValid(graph,i)):
return False
return True
def isBipartite(self, graph: List[List[int]]) -> bool:
self.colors={}
for i in range(len(graph)):
if(i not in self.colors):
self.colors[i]=0
if(not self.isValid(graph,i)):
return False
return True