Is Graph Bipartite

题目
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.

思路
Start with some vertex v, add it to some group 1.
dfs traverse the graph starting with vertex v, look at the edges along the traversal.
Say there is an edge (v,u), then we should put u into group 2 because it has to be in a different group than v. If we ever see the case that we should put a vertex into group X, but it actually already exists in group Y, then we reach a conflict. Therefore we know the graph is not biparite. Kind of like proof of contradiction isn't it ?

答案

class Solution {
    public boolean isBipartite(int[][] graph) {
        Set<Integer> group1 = new HashSet<>();
        Set<Integer> group2 = new HashSet<>();
        boolean[] visited = new boolean[graph.length];
        boolean b = false, ret = false;
        for(int i = 0; i < graph.length; i++) {
            // Do not consider vertices with no neighbors
            if(graph[i].length == 0) continue;
            if(visited[i]) continue;

            group1.add(i);
            ret = dfs(graph, i, visited, group1, group2);
            if(!ret) return false;            
        }
        return true;
    }
    
    public boolean dfs(int[][] graph, int curr, boolean[] visited, Set<Integer> group1, Set<Integer> group2) {
        boolean ret = true;
        visited[curr] = true;
        
        int[] curr_neighbors = graph[curr];
        for(int i = 0; i < curr_neighbors.length; i++) {
            int neighbor = curr_neighbors[i];
            // edge: curr->neighbor
            if(group1.contains(curr)) {
                if(group1.contains(neighbor)) return false;
                group2.add(neighbor);
            }
            else {
                if(group2.contains(neighbor)) return false;
                group1.add(neighbor);                
            }
            
            if(!visited[neighbor]) {
                ret = dfs(graph, neighbor, visited, group1, group2);
                if(!ret) return false;
            }
        }
        return true;
    }
}