給定一個無向圖graph，當這個圖為二分圖時返回true。
如果我們能將一個圖的節點集合分割成兩個獨立的子集A和B，并使圖中的每一條邊的兩個節點一個來自A集合，一個來自B集合，我們就將這個圖稱為二分圖。
graph將會以鄰接表方式給出，graph[i]表示圖中與節點i相連的所有節點。每個節點都是一個在0到graph.length-1之間的整數。這圖中沒有自環和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重復的值。
示例 1:
輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋:
我們可以將節點分成兩組: {0, 2} 和 {1, 3}。
廣度優先搜索代碼
class Solution {public boolean isBipartite(int[][] graph) {int[] color=new int[graph.length];//顏色數組for(int i=0;i<graph.length;i++){if(color[i]!=0) continue;//已經染色了LinkedList<Integer> queue=new LinkedList<>();queue.add(i);color[i]=1;while (!queue.isEmpty()){int cur=queue.removeFirst();for(int j:graph[cur]){if(color[j]==0) {//未染色color[j]=-color[cur];queue.add(j);}else if(color[cur]==color[j])//顏色相同return false;}}}return true;}
}
深度優先搜索代碼
class Solution {public boolean isBipartite(int[][] graph) {int[] color=new int[graph.length];for(int i=0;i<graph.length;i++)if(!dfs(graph,color,i,0))return false;return true;}public boolean dfs(int[][] graph,int[] color,int i,int lastcolor) {if(color[i]!=0) return color[i]!=lastcolor;//已經染色color[i]= lastcolor==1?2:1;//給該點染色for(int j:graph[i])//給其他點染色if(!dfs(graph,color,j,color[i])) return false;return true;}
}
