Given a 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 ubsets.
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. 这道题其实挺简单的。需要注意的是这里的 bipartite 并不是词典上的定义，而是它这里的定义。也就是，把所有的点放入两个 set，要保证，一条边的两个点m、n，如果 m 点在集合 A 中，那么 n 点应该在集合 B 中。
我的思路是，拿出 i 和 graph[i][j]，判断 i 点是在集合 A 还是集合 B 中。如果之前已经把 i 点放入了集合 A 中，设置 belongTo=1。如果之前把 graph[i][j] 中的任何一点放入了集合 A 中，那么 i 点应当放在集合 B 中，设置 belongTo=2。如果发现 belongTo=-1,即之前并没有放入 i 点和所有的 graph[i][j] 点，那么我们就可以随便放，那就把 i 放入集合 A，把所有的 graph[i][j] 放入集合 B 就好了。(因为之前没遇到过这些点，所以并不会影响之前的结果。而之后的点自会判断与这些点的关系，加入相应的集合。）
package leetcode; import java.util.HashSet; import java.util.Set; public class Is_Graph_Bipartite_785 { public boolean isBipartite(int[][] graph) { Set<Integer> setA = new HashSet<>(); Set<Integer> setB = new HashSet<>(); for (int i = 0; i < graph.length; i++) { int belongTo = -1; // 判断 i 是belongTo哪个集合 if (setA.contains(i)) { belongTo = 1; } for (int j = 0; j < graph[i].length; j++) { if (setA.contains(graph[i][j])) { belongTo = 2; break; } } if (belongTo == -1) {// 当前set里的数与当前点无关，所以belongTo放在哪里都没关系 setA.add(i); for (int j = 0; j < graph[i].length; j++) { setB.add(graph[i][j]); } } else if (belongTo == 1) { for (int j = 0; j < graph[i].length; j++) { if (setA.contains(graph[i][j])) { return false; } else { setB.add(graph[i][j]);// 无论有没有，都加，反正不会重复 } } } else {// belongTo==2 setB.add(i); for (int j = 0; j < graph[i].length; j++) { if (setB.contains(graph[i][j])) { return false; } else { setA.add(graph[i][j]);// 无论有没有，都加，反正不会重复 } } } } return true; } public static void main(String[] args) { // TODO Auto-generated method stub Is_Graph_Bipartite_785 is=new Is_Graph_Bipartite_785(); int[][] graph=new int[][]{ {1,2,3},{0,2},{0,1,3},{0,2} }; System.out.println(is.isBipartite(graph)); } }我博客写的时间，并没有大神的discuss放出来。所以先放这，等之后再看大神上传的discuss。https://leetcode.com/problems/is-graph-bipartite/discuss/
