886. Possible Bipartition

 1 class Solution {
 2     int[] colors;
 3     public boolean possibleBipartition(int N,int[][] dislikes) {
 4         if(dislikes.length == 0) return true;
 5         HashMap<Integer,List<Integer>> graph = new HashMap<>();
 6         for(int[] dislike : dislikes){
 7             if(!graph.containsKey(dislike[0])){
 8                 graph.put(dislike[0],new ArrayList<>());
 9             }
10             if(!graph.containsKey(dislike[1])){
11                 graph.put(dislike[1],new ArrayList<>());
12             }
13             graph.get(dislike[0]).add(dislike[1]);
14             graph.get(dislike[1]).add(dislike[0]);
15         }
16         colors = new int[N+1];
17         for(int i = 1; i <= N; i++){
18             if(colors[i] == 0){
19                 if(!dfs(graph,i,1)){
20                     return false;
21                 }
22             }
23             
24         }
25         return true;
26         
27         
28     }
29     
30     public boolean dfs(HashMap<Integer,List<Integer>> graph,int num,int color){
31         if(colors[num] == 0){
32             colors[num] = color;
33         }else if(colors[num] != color){
34             return false;
35         }else{
36             return true;
37         }
38         if(!graph.containsKey(num)) return true;
39         List<Integer> list = graph.get(num);
40         for(int person : list){
41             if(dfs(graph,person,-color) == false){
42                 return false;
43             }
44         }
45         return true;
46         
47     }
48 }