Solution: Possible Bipartition

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Possible Bipartition

Table of Contents

Contents are not accessible

Problem Statement

There are n people (labeled from 1 to n), and need to split them 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] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if you can divide each person into two groups in this way. Otherwise, return false.

Examples

Example 1

Input: n = 5, dislikes = [[1, 2], [2, 3], [3, 4], [4, 5]]
Expected Output: true
Justification: We can split the group into two sets: {1, 3, 5} and {2, 4}. Each person in one group dislikes only those in the other group.

Example 2

Input: n = 6, dislikes = [[1, 2], [2, 4], [4, 6],[4, 5], [5, 6]]
Expected Output: false
Justification: It's impossible to split all persons in 2 parts.

Example 3

Input: n = 3, dislikes = [[1, 2], [1, 3]]
Expected Output: true
Justification: We can split the group into two sets: {1} and {2, 3}. Each person in one group dislikes only those in the other group.

Constraints:

1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= ai < bi <= n
All the pairs of dislikes are unique.

Solution

To solve this problem, we can use the Union-Find algorithm. The Union-Find algorithm helps in managing and merging disjoint sets efficiently. In this problem, we treat each person as a node and each dislike relationship as an edge. The goal is to check if the graph can be colored using two colors without any two adjacent nodes having the same color, which is equivalent to checking if the graph is bipartite.

The Union-Find algorithm helps in grouping nodes and efficiently checking if they belong to the same set or different sets. This approach is effective because it provides a clear way to manage groupings and detect cycles, which indicate that a bipartite split is not possible.

Step-by-Step Algorithm

Initialization:
- Create a UnionFind class to manage the union-find operations.
- Initialize parent and rank arrays for union-find operations.
- Implement find function with path compression.
- Implement union function with union by rank.
Build Adjacency List:
- Initialize an empty adjacency list using a map to store dislikes for each person.
- Iterate over each pair in the dislikes array.
- For each pair [a, b], add b to the list of a and a to the list of b in the adjacency list.
Check Possible Bipartition:
- Initialize a UnionFind instance for n+1 elements.
- Iterate over each person from 1 to n.
  - For each person, check if they have dislikes in the adjacency list.
  - Iterate over the the dislikes for the current person.
  - For each dislike, check if the current person and the dislike are in the same set using the find function.
  - If they are in the same set, return false (not possible to partition).
  - Otherwise, union the first dislike with the current dislike.
Return True:
- If all checks pass, return true (possible to partition).

Algorithm Walkthrough

Input:- n = 5, dislikes = [[1, 2], [2, 3], [3, 4], [4, 5]]

Initialization:
- Create UnionFind with size 6 (n + 1).
- Initialize parent array: [0, 1, 2, 3, 4, 5].
- Initialize rank array: [0, 0, 0, 0, 0, 0].
Build Adjacency List:
- Iterate over dislikes:
  - For [1, 2]: adj becomes {1: [2], 2: [1]}.
  - For [2, 3]: adj becomes {1: [2], 2: [1, 3], 3: [2]}.
  - For [3, 4]: adj becomes {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}.
  - For [4, 5]: adj becomes {1: [2], 2: [1, 3], 3: [2, 4], 4: [3, 5], 5: [4]}.
Check Possible Bipartition:
- Person 1:
  - Iterate over neighbors of 1: [2].
  - Check if 1 and 2 are in the same set using find:
    - find(1) returns 1.
    - find(2) returns 2.
  - They are not in the same set, union 2 with 2.
  - Union operation:
    - union(2, 2) does nothing as they are already in the same set.
  - parent array: [0, 1, 2, 3, 4, 5].
  - rank array: [0, 0, 0, 0, 0, 0].
- Person 2:
  - Iterate over neighbors of 2: [1, 3].
  - Check if 2 and 1 are in the same set using find:
    - find(2) returns 2.
    - find(1) returns 1.
  - They are not in the same set, union 1 with 1, which won't do anything.
  - Union operation:
    - find(1) returns 1.
    - find(3) returns 3.
    - Union 1 and 3: parent[3] = 1, rank[1] = 1.
  - parent array: [0, 1, 2, 1, 4, 5].
  - rank array: [0, 1, 0, 0, 0, 0].
- Person 3:
  - Iterate over neighbors of 3: [2, 4].
  - Check if 3 and 2 are in the same set using find:
    - find(3) returns 1.
    - find(2) returns 2.
  - They are not in the same set, union 2 with 4.
  - Union operation:
    - find(2) returns 2.
    - find(4) returns 4.
    - Union 2 and 4: parent[4] = 2, rank[2] = 1.
  - parent array: [0, 1, 2, 1, 2, 5].
  - rank array: [0, 1, 1, 0, 0, 0].
- Person 4:
  - Iterate over neighbors of 4: [3, 5].
  - Check if 4 and 3 are in the same set using find:
    - find(4) returns 2.
    - find(3) returns 1.
  - They are not in the same set, union 3 with 5.
  - Union operation:
    - find(3) returns 1.
    - find(5) returns 5.
    - Union 3 and 5: parent[5] = 1, rank[1] = 2.
  - parent array: [0, 1, 2, 1, 2, 1].
  - rank array: [0, 2, 1, 0, 0, 0].
- Person 5:
  - Iterate over neighbors of 5: [4].
  - Check if 5 and 4 are in the same set using find:
    - find(5) returns 1.
    - find(4) returns 2.
  - They are not in the same set, union 4 with 4.
  - Union operation:
    - union(4, 4) does nothing as they are already in the same set.
  - parent array: [0, 1, 2, 1, 2, 1].
  - rank array: [0, 2, 1, 0, 0, 0].
Return True:
- No conflicts found, return true.

Code

Python3

. . . .

Complexity Analysis

Time Complexity

Union-Find Initialization: Initializing the parent and rank arrays takes $O(n)$ .
Building the Adjacency List: Iterating through the dislikes array to build the adjacency list takes $O(E)$ , where $(E)$ is the number of dislikes.
Union-Find Operations:
- Find Operation: Each find operation takes $O(\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function, which is very slow-growing and practically constant for all reasonable inputs.
- Union Operation: Each union operation also takes $O(\alpha(n))$ time.
Total Time Complexity: Since we perform union and find operations on each edge in the dislikes array, the total time complexity is $O(E \cdot \alpha(n)) + O(n) \approx O(E + N)$ , given that $\alpha(n)$ is nearly constant.

Space Complexity

Union-Find Arrays: The parent and rank arrays each take $O(N)$ space.
Adjacency List: The adjacency list takes $O(E)$ space.
Total Space Complexity: The total space complexity is $O(N + E)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible