Friendly Groups

    static Boolean can_be_divided(Integer num_of_people, ArrayList<Integer> dislike1, ArrayList<Integer> dislike2) {
        //Build the graph
        Map<Integer, ArrayList<Integer>> adj_list = new HashMap<>();
        for (int node = 0; node < num_of_people; node++) {
            adj_list.put(node, new ArrayList<Integer>());
        }
        for (int i = 0; i < dislike1.size(); i++) {
            adj_list.get(dislike1.get(i)).add(dislike2.get(i));
            adj_list.get(dislike2.get(i)).add(dislike1.get(i));
        }

        int[] visited = new int[num_of_people];
        int[] subset = new int[num_of_people];
        for (int node = 0; node < num_of_people; node++) {
            if (visited[node] == 0) {
                subset[node] = 0;
                if (!dfs(node, visited, subset, adj_list)) {
                    return false;
                }
            }
        }

        return true;
    }

    static Boolean dfs(int node, int[] visited, int[] subset, Map<Integer, ArrayList<Integer>> adj_list) {
        visited[node] = 1;

        for (int neighbor : adj_list.get(node)) {
            if (visited[neighbor] == 0) {
                //assign the opposite subset
                subset[neighbor] = 1 - subset[node];

                if (!dfs(neighbor, visited, subset, adj_list)) {
                    return false;
                }
            } else {
                //if we have seen this node before,
                //is it in the same subset, if so, return false
                if (subset[node] == subset[neighbor]) {
                    return false;
                }
            }
        }

        return true;
    }