给定一个graph，true当且仅当它是二分的。
回想一下，如果我们可以将它的一组节点分成两个独立的子集A和B，使得图中的每条边在A中有一个节点，并且在B中有另一个节点，那么图是二分的。
该图形以下列形式给出：graph[i]是j节点之间的边缘i和j存在的索引列表。每个节点是0和之间的整数graph.length - 1。没有自我边缘或平行边缘：graph[i]不包含i，也不包含任何元素两次。
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 ubsets.
这是一道关于二部图的问题。
解题的思路分两部分，首先深度搜索得到连通图，在深度搜索时，对于iscolor数组，第一层标记为1，第二层标记为-1，第三层标记为1......如此往复。然后得到连通图，判断是否为二分图。如果所有的连通图都是二分图，那么返回true。
class Solution { public boolean isBipartite(int[][] graph) { boolean flag=true; int length=graph.length; if(length<3) return true; //初始化用来表示是否访问过,0表示未访问, 1,-1代表两种上色颜色 int[] iscolor=new int[length]; for(int i=0;i<length;i++) { if(iscolor[i]==0) { //进行深度优先搜索得到连通图 Set<Integer> set=new HashSet<Integer>(); GetGraphbyDFS(graph,iscolor,i,set,1); if(!isvalid(set,graph,iscolor)) return false; } } return true; } private boolean isvalid(Set<Integer> set, int[][] graph, int[] iscolor) { // 判断是否是二分图 if(set.size()<=2) return true; for(Integer s: set){ for(int i=0;i<graph[s].length;i++) { int index=graph[s][i]; if(iscolor[index]==iscolor[s]) return false; } } return true; } private void GetGraphbyDFS(int[][] graph, int[] iscolor, int index, Set<Integer> set,int color) { // TODO Auto-generated method stub set.add(index); iscolor[index]=color; for(int i=0;i<graph[index].length;i++) { if(iscolor[graph[index][i]]==0) { GetGraphbyDFS(graph,iscolor,graph[index][i],set,-color);//下一次更换color } } } }
