202. Possible Bipartition
π LeetCode Problem: 886. Possible Bipartition
π Difficulty: Medium
π·οΈ Topics: Graph, BFS, DFS, Union-Find, Bipartite
Problem Statement
We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
Given the integer n and the array dislikes where dislikes[i] = [aα΅’, bα΅’] indicates that the person labeled aα΅’ does not like the person labeled bα΅’, return true if it is possible to split everyone into two groups in this way.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Visual:
Person 1 dislikes 2 and 3
Person 2 dislikes 1 and 4
Graph (dislike edges):
1 --- 2
| |
3 4
Output: true
Explanation:
Group A: {1, 4}
Group B: {2, 3}
Check dislikes:
1-2: Different groups β
1-3: Different groups β
2-4: Different groups β
All dislikes satisfied! Possible! β
Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Visual:
Everyone dislikes everyone else!
Triangle:
1 --- 2
\ /
\ /
3
Output: false
Explanation:
If 1 is in group A, then 2 and 3 must be in group B.
But 2 and 3 dislike each other!
Both in B β violates constraint! β
Triangle (odd cycle) β Impossible!
Example 3:
Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Visual:
5-cycle (odd cycle):
1 --- 2
| |
5 --- 3
\ /
\ /
4
Output: false
Explanation:
Odd cycle (5 nodes) β Cannot bipartition!
Constraints:
- 1 <= n <= 2000
- 0 <= dislikes.length <= 10β΄
- dislikes[i].length == 2
- 1 <= aα΅’ < bα΅’ <= n
- All the pairs of dislikes are unique.
π³ Visual Understanding - The Complete Picture
The Problem We're Solving π€
Split people into TWO groups: π¨
Constraint: People who dislike each other β DIFFERENT groups!
This is EXACTLY bipartite checking! π―
Think of it as:
Dislike edge = Connection in graph
Can we 2-color this graph?
Example 1: POSSIBLE β
dislikes = [[1,2],[1,3],[2,4]]
Build graph:
1 --- 2
| |
3 4
Try 2-coloring:
1: Red π΄
2: Blue (dislikes 1) π΅
3: Blue (dislikes 1) π΅
4: Red (dislikes 2) π΄
Success! No conflicts! β
Group A (Red): {1, 4}
Group B (Blue): {2, 3}
Example 2: IMPOSSIBLE β
dislikes = [[1,2],[1,3],[2,3]]
Triangle (odd cycle):
1 --- 2
\ /
3
Try 2-coloring:
1: Red
2: Blue (dislikes 1)
3: Blue (dislikes 1)
But 2 and 3 dislike each other!
Both Blue β Conflict! β
Odd cycle β Impossible!
Connection to Problem 201 π
Problem 201: Is Graph Bipartite?
- Given: Adjacency list graph
- Check: Can 2-color the graph?
Problem 202: Possible Bipartition
- Given: List of dislike pairs
- Check: Can 2-color the graph?
SAME PROBLEM! π―
Differences:
1. Input format: pairs vs adjacency list
2. Node numbering: 1-indexed vs 0-indexed
3. Semantic: "dislikes" vs "connected"
Core algorithm: IDENTICAL!
Build graph from pairs β Run bipartite check!
The Dislike Graph π
Key insight: Dislike = Edge in graph!
Example: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Step 1: Build adjacency list
1: [2, 3]
2: [1, 4]
3: [1]
4: [2]
Step 2: Check if bipartite
Same algorithm as Problem 201!
BFS or DFS 2-coloring
Step 3: Return result
No odd cycle β true β
Has odd cycle β false β
It's bipartite checking with different wrapper! π
π§ The Journey - Building Intuition
Part 1: Understanding "Dislike" Constraint π
π Real-world scenario:
You're organizing a school event with 2 rooms:
- Room A and Room B
- People who dislike each other can't be in same room
Question: Can we split everyone into 2 rooms?
Example 1: YES β
Alice dislikes Bob
Alice dislikes Charlie
Bob dislikes David
Room A: {Alice, David}
Room B: {Bob, Charlie}
Check:
Alice β Bob: Different rooms β
Alice β Charlie: Different rooms β
Bob β David: Different rooms β
Success!
Example 2: NO β
Alice dislikes Bob
Alice dislikes Charlie
Bob dislikes Charlie
If Alice β Room A
Then Bob, Charlie β Room B
But Bob and Charlie dislike each other!
Impossible! Triangle conflict!
This is EXACTLY our problem! π―
Part 2: From Dislikes to Graph π
π How to model this?
Observation:
If person A dislikes person B
β A and B must be in different groups
β A and B are "connected" by dislike edge
β This forms a GRAPH!
Transformation:
People β Nodes
Dislike pair β Edge
Example:
n = 4
dislikes = [[1,2],[1,3],[2,4]]
Graph:
Nodes: 1, 2, 3, 4
Edges: 1-2, 1-3, 2-4
Build adjacency list:
1: [2, 3]
2: [1, 4]
3: [1]
4: [2]
Now we have a graph! π
Question becomes: Is this graph bipartite?
Part 3: Why Bipartite Check Works π―
π Connection to bipartite graphs:
Bipartite definition:
Can partition nodes into 2 sets A and B
Such that every edge connects A β B
No edges within A or within B
Our problem:
Can partition people into 2 groups
Such that every dislike connects different groups
No dislikes within same group
IDENTICAL! π―
If graph is bipartite:
Set A = Group 1
Set B = Group 2
All dislike edges cross groups β
If graph is NOT bipartite:
Has odd cycle
Can't 2-color
Can't split into 2 groups β
Bipartite check solves our problem! π‘
Part 4: Handle 1-Indexing β οΈ
π Important detail: People numbered 1 to n!
Problem 201: Nodes 0 to n-1 (0-indexed)
Problem 202: Nodes 1 to n (1-indexed)
Solution: Adjust indexing!
Option 1: Create graph of size n+1
Use indices 1 to n directly
Index 0 unused
graph = new ArrayList[n + 1]
for i from 0 to n: create list
Easy, wastes one slot
Option 2: Convert to 0-indexed
Map person i to index i-1
graph = new ArrayList[n]
for [a, b] in dislikes:
graph[a-1].add(b-1)
graph[b-1].add(a-1)
More efficient, needs careful mapping
We'll use Option 1 (simpler)! β¨
π― Approach 1: BFS (Most Intuitive!)
The Key Insight π‘
Same as Problem 201 with different input! Build graph from dislike pairs π, then run BFS 2-coloring π¨! People who dislike each other must have different colors π΄π΅! Handle 1-indexing carefully (graph size n+1, use indices 1 to n) β οΈ! Time: O(n + E) where E = dislikes β‘, Space: O(n + E) π¦!
Direct application of bipartite! π
Complete Implementation
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// BFS BIPARTITE CHECK π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Same algorithm as Problem 201!
// Just different input format
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// STEP 1: BUILD GRAPH FROM DISLIKE PAIRS π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Use size n+1 for 1-indexed nodes
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// Add dislike edges (undirected)
for (int[] dislike : dislikes) {
int a = dislike[0];
int b = dislike[1];
graph.get(a).add(b);
graph.get(b).add(a);
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// STEP 2: 2-COLOR CHECK USING BFS π¨
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
int[] color = new int[n + 1];
Arrays.fill(color, -1); // -1 = uncolored
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// CHECK EACH COMPONENT (might be disconnected) πΊοΈ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
for (int person = 1; person <= n; person++) {
if (color[person] != -1) {
continue; // Already colored
}
// βββββββββββββββββββββββββββββββββββββββββββββββ
// START BFS FROM THIS PERSON π
// βββββββββββββββββββββββββββββββββββββββββββββββ
Queue<Integer> queue = new LinkedList<>();
queue.offer(person);
color[person] = 0; // Color as 0 (Group A)
while (!queue.isEmpty()) {
int current = queue.poll();
int currentColor = color[current];
int oppositeColor = 1 - currentColor;
// βββββββββββββββββββββββββββββββββββββββββββ
// PROCESS ALL DISLIKES π
// βββββββββββββββββββββββββββββββββββββββββββ
for (int disliked : graph.get(current)) {
if (color[disliked] == -1) {
// βββββββββββββββββββββββββββββββββββ
// UNCOLORED: Put in opposite group
// βββββββββββββββββββββββββββββββββββ
color[disliked] = oppositeColor;
queue.offer(disliked);
} else if (color[disliked] == currentColor) {
// βββββββββββββββββββββββββββββββββββ
// CONFLICT! β
// They dislike each other but same group!
// βββββββββββββββββββββββββββββββββββ
return false;
}
// else: already in opposite group β
}
}
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// NO CONFLICTS! Can bipartition! β
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
return true;
}
}
Why This Works π―
Graph building from pairs: π - Each dislike pair creates edge in both directions - Undirected graph (if A dislikes B, then B dislikes A) - Standard adjacency list representation
Same bipartite logic: π¨ - Try to 2-color the graph - Adjacent nodes (who dislike each other) must have different colors - Different colors = different groups!
1-indexed handling: β οΈ - Graph size n+1 (index 0 unused) - Loop from person = 1 to n - Direct indexing, no conversion needed!
π― Approach 2: DFS (Clean & Recursive!)
The Key Insight π‘
Recursive 2-coloring π! Color current person, recursively color disliked people with opposite color π¨! If disliked person already has SAME color β impossible! β Time: O(n + E) β‘, Space: O(n + E) π¦!
Elegant and concise! β¨
Complete Implementation
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// DFS BIPARTITE CHECK π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Build graph (1-indexed)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int[] dislike : dislikes) {
graph.get(dislike[0]).add(dislike[1]);
graph.get(dislike[1]).add(dislike[0]);
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// DFS 2-COLORING π¨
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
int[] color = new int[n + 1];
Arrays.fill(color, -1);
for (int person = 1; person <= n; person++) {
if (color[person] == -1) {
if (!dfs(graph, person, 0, color)) {
return false; // Conflict found!
}
}
}
return true; // All components bipartite!
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββββββ
// DFS: Try to color 'person' with given 'c' π¨
// βββββββββββββββββββββββββββββββββββββββββββββββββββββββ
private boolean dfs(List<List<Integer>> graph, int person,
int c, int[] color) {
color[person] = c;
for (int disliked : graph.get(person)) {
if (color[disliked] == -1) {
// Uncolored: recursively color with opposite
if (!dfs(graph, disliked, 1 - c, color)) {
return false;
}
} else if (color[disliked] == c) {
// Conflict! Same color!
return false;
}
}
return true;
}
}
π― Approach 3: Union-Find (Alternative Perspective!)
The Key Insight π‘
Group enemies together! π Key observation: All people disliked by person X must be in SAME group (opposite from X) π₯! Union all of X's dislikes together π€! Then check: If any person is in same group as someone they dislike β impossible! β Time: O(n + E Γ Ξ±(n)) β‘, Space: O(n) π¦!
Structural checking! π
Complete Implementation
class Solution {
private int[] parent;
private int[] rank;
public boolean possibleBipartition(int n, int[][] dislikes) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// UNION-FIND APPROACH π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Key insight: All enemies of a person must be
// in the SAME group (opposite from that person)
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Build adjacency list (1-indexed)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int[] dislike : dislikes) {
graph.get(dislike[0]).add(dislike[1]);
graph.get(dislike[1]).add(dislike[0]);
}
// Initialize Union-Find (1-indexed)
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// STEP 1: UNION ALL ENEMIES OF EACH PERSON π€
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
for (int person = 1; person <= n; person++) {
List<Integer> enemies = graph.get(person);
if (enemies.size() == 0) continue;
// Union all enemies together
// (they all must be in opposite group from person)
for (int i = 1; i < enemies.size(); i++) {
union(enemies.get(0), enemies.get(i));
}
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// STEP 2: CHECK FOR CONFLICTS β
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
for (int person = 1; person <= n; person++) {
for (int enemy : graph.get(person)) {
if (find(person) == find(enemy)) {
// Person and their enemy in same group!
// Conflict! Cannot bipartition!
return false;
}
}
}
return true; // No conflicts!
}
private int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
private void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
π Detailed Dry Run - BFS Approach
Let's trace on:
n = 4
dislikes = [[1,2],[1,3],[2,4]]
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β STEP 1: BUILD GRAPH β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Graph (adjacency list, 1-indexed):
1: [2, 3]
2: [1, 4]
3: [1]
4: [2]
Visual:
1 --- 2
| |
3 4
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β STEP 2: BFS 2-COLORING CHECK β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Initialize:
color = [-1, -1, -1, -1, -1] (index 0 unused)
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β START FROM PERSON 1 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β color[1] = -1 (uncolored), start BFS β
β β
β Initialize BFS: β
β Queue: [1] β
β color[1] = 0 (Group A) π΄ β
β β
β State: color = [-1, 0, -1, -1, -1] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β PROCESS PERSON 1 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Dequeue: 1 β
β Current color: 0 β
β Opposite color: 1 β
β β
β Dislikes of 1: [2, 3] β
β β
β Process person 2: β
β color[2] = -1 (uncolored) β
β Assign opposite: color[2] = 1 (Group B) π΅ β
β Add to queue β
β β
β Process person 3: β
β color[3] = -1 (uncolored) β
β Assign opposite: color[3] = 1 (Group B) π΅ β
β Add to queue β
β β
β Queue: [2, 3] β
β State: color = [-1, 0, 1, 1, -1] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β PROCESS PERSON 2 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Dequeue: 2 β
β Current color: 1 β
β Opposite color: 0 β
β β
β Dislikes of 2: [1, 4] β
β β
β Process person 1: β
β color[1] = 0 (already colored) β
β Check: 0 == 1? NO! Different β
β
β β
β Process person 4: β
β color[4] = -1 (uncolored) β
β Assign opposite: color[4] = 0 (Group A) π΄ β
β Add to queue β
β β
β Queue: [3, 4] β
β State: color = [-1, 0, 1, 1, 0] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β PROCESS PERSON 3 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Dequeue: 3 β
β Current color: 1 β
β β
β Dislikes of 3: [1] β
β β
β Process person 1: β
β color[1] = 0 (already colored) β
β Check: 0 == 1? NO! Different β
β
β β
β Queue: [4] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β PROCESS PERSON 4 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Dequeue: 4 β
β Current color: 0 β
β β
β Dislikes of 4: [2] β
β β
β Process person 2: β
β color[2] = 1 (already colored) β
β Check: 1 == 0? NO! Different β
β
β β
β Queue: [] (empty!) β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
BFS complete for this component!
All remaining persons (none) already colored.
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β FINAL RESULT: TRUE β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ£
β β
β Final coloring: β
β color = [-1, 0, 1, 1, 0] β
β (unused, 1, 2, 3, 4) β
β β
β Group A (color 0): {1, 4} π΄ β
β Group B (color 1): {2, 3} π΅ β
β β
β Check all dislikes: β
β 1-2: Different groups β
β
β 1-3: Different groups β
β
β 2-4: Different groups β
β
β β
β All dislikes satisfied! β
β Bipartition is POSSIBLE! Return true! π β
β β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
π Key Observations:
-
Graph building first: π Convert dislike pairs to adjacency list
-
1-indexed handling: β οΈ Graph size n+1, loop from 1 to n
-
BFS alternates colors: π Level by level, opposite colors assigned
-
All checks pass: β No adjacent nodes have same color
-
Even cycle detected: π 4-node cycle is even, bipartition works!
π Complexity Analysis
BFS/DFS Approaches
Time Complexity: O(n + E) β‘
Where:
n = number of people
E = number of dislikes
Build graph: O(E)
Each dislike creates 2 edges
BFS/DFS traversal: O(n + E)
Visit each person once: O(n)
Check each dislike once: O(E)
Total: O(n + E)
Example: n = 2000, E = 10000
Operations: 12000 (very fast!) β
Space Complexity: O(n + E) π¦
Graph adjacency list: O(n + E)
n lists, total E edges
Color array: O(n)
Queue (BFS): O(n)
Recursion (DFS): O(n)
Total: O(n + E) π¦
Union-Find Approach
Time Complexity: O(n + E Γ Ξ±(n)) β‘
Build graph: O(E)
Union operations: O(E Γ Ξ±(n))
Check conflicts: O(E Γ Ξ±(n))
Total: O(E Γ Ξ±(n)) β O(E)
Slightly slower but still efficient!
Space Complexity: O(n + E) π¦
Graph: O(n + E)
Parent array: O(n)
Rank array: O(n)
Total: O(n + E) π¦
π Quick Revision Notes
π― Core Concept
Possible Bipartition = Problem 201 with different input! π― Given dislike pairs, build graph where dislike = edge π! Then run bipartite check (BFS/DFS 2-coloring) π¨! People who dislike each other must be in different groups (different colors) π΄π΅! Handle 1-indexing - graph size n+1, use indices 1 to n β οΈ! Same algorithm as Problem 201 - just build graph first! Time: O(n+E) β‘, Space: O(n+E) π¦!
β‘ Quick Implementation (BFS)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
// Key concept: colouring
// If a node is not colored (initial), mark it RED.
// If its colored RED, color it BLUE. Or if its colored BLUE, color it RED.
// If its already colored, it should be opposite
// Assumptions: uncolored: -1, RED: 0, BLUE: 1
// Note: need to create adj list.
List<List<Integer>> adjList = getAdjList(n, dislikes);
// // Approach 1 - BFS
// return bfs(n, adjList);
// Approach 2 - DFS
return dfs(n, adjList);
}
private List<List<Integer>> getAdjList(int n, int[][] a) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
for (int[] edge : a) {
list.get(edge[0]).add(edge[1]);
list.get(edge[1]).add(edge[0]);
}
return list;
}
private boolean dfs(int n, List<List<Integer>> adjList) {
int[] color = new int[n + 1];
Arrays.fill(color, -1);
for (int i = 1; i <= n; i++) {
if (color[i] == -1) { // color it only when its uncolored
color[i] = 0; // lets start with RED or 0 for node 0.
if (!dfsUtil(i, color, adjList)) {
return false;
}
}
}
return true;
}
private boolean dfsUtil(int start, int[] color, List<List<Integer>> adjList) {
int currNodeColor = color[start];
int nextNodeColor = 1 - currNodeColor; // 0 becomes 1 and 1 becomes 0
for (int node : adjList.get(start)) {
if (color[node] == -1) {
color[node] = nextNodeColor;
if (!dfsUtil(node, color, adjList)) {
return false;
}
} else if (color[node] == currNodeColor) {
return false;
}
}
return true;
}
private boolean bfs(int n, List<List<Integer>> list) {
// Initialize all colors with -1
int[] color = new int[n + 1];
Arrays.fill(color, -1);
// Start traversing and coloring each node
for (int i = 1; i <= n; i++) {
// GOTCHA: already colored. Skip it
if (color[i] != -1) {
continue;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
color[i] = 0; // lets start with RED or 0 for node 0.
while (!queue.isEmpty()) {
int currNode = queue.poll();
int currNodeColor = color[currNode];
int nextNodeColor = 1 - currNodeColor; // 0 becomes 1 and 1 becomes 0
for (int j : list.get(currNode)) {
if (color[j] == -1) {
color[j] = nextNodeColor;
queue.offer(j);
} else if (color[j] == currNodeColor) {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.possibleBipartition(4, new int[][] { { 1, 2 }, { 1, 3 }, { 2, 4 } })); // true
System.out.println(s.possibleBipartition(3, new int[][] { { 1, 2 }, { 1, 3 }, { 2, 3 } })); // false
}
}
π Key Insights
Dislike = Edge in Graph: π
Critical transformation:
Dislike pair [A, B]
β A and B must be in different groups
β A and B are connected by edge
β Build undirected graph!
Example:
dislikes = [[1,2],[1,3]]
Graph:
1: [2, 3]
2: [1]
3: [1]
Edge 1-2 means: 1 and 2 different groups
Edge 1-3 means: 1 and 3 different groups
Graph models the constraint! π
Same Algorithm as Problem 201: β»οΈ
The ONLY differences:
1. Input format:
201: graph[][] (adjacency list given)
202: dislikes[][] (pairs given)
β Build graph first!
2. Node numbering:
201: 0 to n-1 (0-indexed)
202: 1 to n (1-indexed)
β Use graph size n+1!
3. Semantics:
201: "connected nodes"
202: "people who dislike each other"
β Same meaning: edge!
Core algorithm: IDENTICAL! π―
1-Indexed Handling: β οΈ
People numbered 1 to n!
Solution:
graph = new ArrayList[n + 1]
color = new int[n + 1]
Loop: for person = 1; person <= n
Index 0: unused but allocated
Indices 1 to n: actual people
Why not convert to 0-indexed?
- More code changes needed
- Easy to make mistakes
- Simpler to use n+1 size! β
Remember: loop starts at 1, not 0!
Three Approaches, Same Result: π―
BFS (Easiest):
β
Level-by-level, intuitive
β
Iterative, no stack overflow
DFS (Most concise):
β
Recursive elegance
β
Less code
Union-Find (Different view):
β
Structural checking
β
Group enemies together
All O(n+E) time! Choose preference! βοΈ
πͺ Memory Aid
"Dislike is an edge, build the graph" π
"One-indexed, don't lose track!" β οΈ
"Same as 201, just change the path" π
"Two-color check, stay on track!" π¨ β¨
β οΈ Don't Forget
- Build graph FIRST - from dislike pairs to adjacency list! π
- 1-indexed people - use graph[n+1], loop from 1 to n! β οΈ
- Undirected graph - add edge in BOTH directions! βοΈ
- Same bipartite check - exactly like Problem 201! π
- Handle disconnected - check each uncolored person! πΊοΈ
- Index 0 unused - people start at 1! π
π Congratulations!
You've mastered Bipartite Application Problem! π
What You Learned:
β
Problem transformation - dislikes β graph edges! π
β
Pattern recognition - same as Problem 201! π
β
Input handling - pairs to adjacency list! π
β
1-indexed graphs - size n+1, loop from 1! β οΈ
β
Same algorithm - bipartite check works! π¨
β
Three approaches - BFS, DFS, Union-Find! π
The Beautiful Connection:
Problem Pattern: Constraint Satisfaction
Problem 201: Is Graph Bipartite?
- Direct bipartite check
- Graph given as adjacency list
- 0-indexed nodes
Problem 202: Possible Bipartition
- Same bipartite check!
- Graph built from dislike pairs
- 1-indexed people
SAME ALGORITHM! π―
Key skill: Recognizing the pattern!
"Two groups, no internal connections"
β Think BIPARTITE! π‘
Applications:
β
Team division with conflicts
β
Task scheduling with constraints
β
Resource allocation
β
Conflict resolution
β
Graph coloring
Bipartite checking = powerful tool! π
Twenty-five problems completed! π
Bipartite pattern recognition mastered! Same algorithm, different wrapper! πͺβ¨π―π¨ππ