886. Possible Bipartition

Link

Solution

Color each node, and make sure dislike[0] and dislike[1] must have a different color.

If that can't be done, then return false, otherwise, return true.

Key point is to make sure the Map contains two directions information.

    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] color = new int[N+1];
        
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for(int[] dislike : dislikes){
        
            //Need to make the map has two directions information!
            if(!map.containsKey(dislike[0])){
                map.put(dislike[0], new LinkedList<Integer>());
            }
            if(!map.containsKey(dislike[1])){
                map.put(dislike[1], new LinkedList<Integer>());
            }
            map.get(dislike[0]).add(dislike[1]);
            map.get(dislike[1]).add(dislike[0]);

        }
        
        //0: unvisited, 1 : zone1, -1: zone 2
        for(int i : map.keySet()){
            if(color[i] == 0){
                if(!dfs(map, color , i, 1)) return false;   
            }
        }
        return true;
    }
               
    public boolean dfs(HashMap<Integer, List<Integer>> map, int[] color, int i, int newColor){
        
        if(color[i] != 0 && color[i] != newColor) return false;
        if(color[i] == newColor) return true;
        color[i] = newColor;
        
        if(map.get(i) != null){
            for(int p : map.get(i)){
                if(!dfs(map, color, p, -newColor)) return false;
            }
        }
        return true;
    }