1. Problem Description

You are given an integer n, representing the number of people labeled from 1 to n.
You are also given an array dislikes, where dislikes[i] = [a, b] means that person a and person b dislike each other.

Your task is to determine whether it is possible to divide all people into two groups such that:

• No pair of people in the same group dislike each other.

If this arrangement is possible, return true; otherwise, return false.

---

2. Example

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true

Explanation:
Group 1: [1, 4]
Group 2: [2, 3]
No pair in the same group dislikes each other.

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Explanation:
No matter how we divide, at least one pair that dislikes each other will end up in the same group.

---

3. Intuition

This problem can be represented using a graph:

• Each person is a node.
• Each dislike relationship [a, b] is an undirected edge between a and b.

We need to determine whether this graph is bipartite — that is, whether we can color all nodes using two colors such that no two adjacent nodes share the same color.

If we can assign such colors, it means we can separate people into two groups, and the answer is true.

If there’s a conflict (an edge connects two nodes with the same color), then the graph is not bipartite, and the answer is false.

---

4. Graph Theory Connection

A bipartite graph can be colored with two colors (say, 0 and 1) such that no two adjacent vertices have the same color.

Hence, the problem reduces to:

“Can we color this graph with two colors such that no connected pair has the same color?”

This can be checked using Depth-First Search (DFS) or Breadth-First Search (BFS).

---

5. Approach: BFS/DFS Graph Coloring

Step 1: Build an adjacency list

We first create an adjacency list to represent dislike relationships.

Step 2: Use an array color[]

• color[i] = 0 means uncolored.
• color[i] = 1 means Group A.
• color[i] = -1 means Group B.

Step 3: Traverse each node

Since the graph may not be connected, we need to traverse every node.

For each uncolored node:

• Assign one color (e.g., 1)
• Use DFS or BFS to propagate the opposite color to its neighbors.
• If a neighbor already has the same color, then it’s not possible to partition.

---

6. Step-by-Step Example

Let’s dry run for:

n = 4
dislikes = [[1,2], [1,3], [2,4]]

Adjacency List:

1 → [2, 3]
2 → [1, 4]
3 → [1]
4 → [2]

Coloring Steps:

• Start with node 1, color it 1.
  • Neighbor 2 → color -1
  • Neighbor 3 → color -1
• Move to node 2
  • Neighbor 1 is color 1 → OK
  • Neighbor 4 → color 1
• Move to node 3
  • Neighbor 1 is color 1 → OK
• Move to node 4
  • Neighbor 2 is color -1 → OK

No conflicts found → Possible Bipartition: true

---

7. Java Implementation (DFS Approach)

import java.util.*;

public class PossibleBipartition {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // Build adjacency list
        for (int[] pair : dislikes) {
            graph.get(pair[0]).add(pair[1]);
            graph.get(pair[1]).add(pair[0]);
        }

        int[] color = new int[n + 1]; // 0 = uncolored, 1 = group A, -1 = group B

        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !dfs(graph, color, i, 1)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] color, int node, int currentColor) {
        color[node] = currentColor;

        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == currentColor) {
                return false; // Conflict found
            }
            if (color[neighbor] == 0 && !dfs(graph, color, neighbor, -currentColor)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        PossibleBipartition solution = new PossibleBipartition();

        int n1 = 4;
        int[][] dislikes1 = {{1,2}, {1,3}, {2,4}};
        System.out.println(solution.possibleBipartition(n1, dislikes1)); // Output: true

        int n2 = 3;
        int[][] dislikes2 = {{1,2}, {1,3}, {2,3}};
        System.out.println(solution.possibleBipartition(n2, dislikes2)); // Output: false
    }
}

---

8. Alternate Approach: BFS (Iterative)

We can also use a BFS approach for coloring.

import java.util.*;

public class PossibleBipartitionBFS {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] pair : dislikes) {
            graph.get(pair[0]).add(pair[1]);
            graph.get(pair[1]).add(pair[0]);
        }

        int[] color = new int[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            if (color[i] != 0) continue;
            queue.add(i);
            color[i] = 1;

            while (!queue.isEmpty()) {
                int curr = queue.poll();
                for (int neighbor : graph.get(curr)) {
                    if (color[neighbor] == color[curr]) {
                        return false;
                    }
                    if (color[neighbor] == 0) {
                        color[neighbor] = -color[curr];
                        queue.add(neighbor);
                    }
                }
            }
        }
        return true;
    }
}

---

9. Complexity Analysis

Aspect	Complexity
Time Complexity	O(N + E) where N = number of people, E = number of dislike pairs
Space Complexity	O(N + E) due to adjacency list and recursion/queue

---

10. Summary

Concept	Description
Problem Type	Graph Coloring (Check for Bipartite Graph)
Approach	DFS or BFS
Key Idea	Assign two groups using two colors; check for conflicts
Data Structure	Adjacency List, Color Array
Time Complexity	O(N + E)
Space Complexity	O(N + E)
Related Problems	785. Is Graph Bipartite?, 994. Rotting Oranges