| 1 | class Solution { |
| 2 | public boolean possibleBipartition(int N, int[][] dislikes) { |
| 3 | int i=0,a=0,b=0; |
| 4 | List<Integer>[] graph=new List[N]; // create adjacancy list |
| 5 | for(i=0; i < N; i++){ |
| 6 | graph[i]=new ArrayList<>(); |
| 7 | } |
| 8 | for(int[] d:dislikes) { |
| 9 | a=d[0]-1; |
| 10 | b=d[1]-1; |
| 11 | graph[a].add(b); //add who dislikes who as edges in graph |
| 12 | graph[b].add(a); |
| 13 | } |
| 14 | int[] groupMap = new int[N]; // store partition here |
| 15 | Arrays.fill(groupMap,-1); |
| 16 | for(i=0;i<N;i++) |
| 17 | if (groupMap[i]==-1 && !dfs(graph,i,0,groupMap)) |
| 18 | return false; // if dfs is false(cant be in same grp) and groupmap is -1, ret false |
| 19 | return true; |
| 20 | } |
| 21 | boolean dfs(List<Integer>[] graph, int src, int group, int[] groupMap) { // recursive depth first search logic |
| 22 | if (groupMap[src]==1-group) |
| 23 | return false; |
| 24 | if (groupMap[src]==group) |
| 25 | return true; |
| 26 | groupMap[src]=group; |
| 27 | for (int v : graph[src]) |
| 28 | if (!dfs(graph,v,1-group,groupMap)) |
| 29 | return false; |
| 30 | return true; |
| 31 | } |
| 32 | } |
nothing calls this directly
no outgoing calls
no test coverage detected