886. Possible Bipartition


Problem Description

The problem presents a scenario where we need to split n people, each labeled uniquely from 1 to n, into two separate groups. These groups could be of any size, which implies that even a single individual in a group is allowable. The key constraint is that some pairs of individuals do not get along, denoted by the dislikes array. Each element of the dislikes array is a subarray of two integers where [a_i, b_i] signifies that person a_i dislikes person b_i, and consequently, they should not end up in the same group.

The task is to determine if it's possible to successfully divide all the people into two such groups where none of the individuals in the same group dislike each other.

Intuition

To intuitively approach the problem, we can consider the 'dislike' relationships as edges in a graph with the people as vertices. If we can color all vertices of this graph using only two colors in such a way that no two adjacent vertices (disliking each other) have the same color, then we can successfully divide the people into two groups—where each color represents a separate group.

The problem thus can be related to a graph theory concept known as bipartite checking. A graph is bipartite if we can split its vertices into two groups such that no edges exist between vertices of the same group.

The solution adopts the union-find algorithm to solve this problem efficiently. Union-find is a data structure that keeps track of elements divided into sets and is capable of efficiently combining these sets and finding representatives of these sets. It can help in the quick determination of whether two elements belong to the same set or not — crucial for us to understand if connecting two individuals (via their dislikes) would create a conflict within a group.

The provided Python solution follows these steps:

  1. Initialize each person's parent as themselves, creating 'n' separate sets.
  2. Iteratively traverse through the dislikes list:
    • For each dislike relationship, find the parents (representatives) of the two individuals.
    • If both individuals already have the same parent, this means they're supposed to be in the same group, indicating a conflict, and thus, bipartition isn't possible.
    • Otherwise, union the sets by assigning one individual's parent as the other individual's dislikes' parent, effectively grouping them in the opposite groups.
  3. If we pass through the dislikes list without encountering any conflicts, a bipartition is possible, and we return True.

The union-find algorithm provides an efficient way to dynamically group the individuals while keeping track of their relationships and allows us to assess the possibility of a bipartition.

Solution Approach

The solution approach relies on the union-find data structure and algorithm to solve the problem. Here is a step-by-step walkthrough of the implementation provided in the reference solution:

  1. Initialize Union-Find Structure: We start by initializing an array p = list(range(n)) where each person is initially set as their own parent. This setup helps us track which group each person belongs to as we progress through the dislikes.

  2. Graph Construction: Using a dictionary g, we map each person to a list of people they dislike (building an adjacency list representation of our graph). The code for a, b in dislikes: a, b = a - 1, b - 1; g[a].append(b); g[b].append(a) populates this dictionary. Note that we use a - 1 and b - 1 because the people are labeled from 1 to n, but Python lists are 0-indexed.

  3. Union-Find Algorithm: The core logic lies in the following part of the code:

    • We iterate over each person using for i in range(n): and then over the list of people each person dislikes using for j in g[i]:.
    • We perform a find operation for both the current person i and the people they dislike j by calling the find() function, which recursively locates the root parent of the given person's set, with path compression. If find(i) is equal to find(j), this would mean attempting to add an edge between two vertices already part of the same group, which isn't allowed; thus, we return False.
    • If there's no immediate conflict, we perform a union operation. We union the set containing the disliked individual j with the next person disliked by i (g[i][0]), ensuring that 'dislikers' and 'dislikees' end up in different sets by having different roots. This is achieved by setting the parent of find(j) to the person that i dislikes first: p[find(j)] = find(g[i][0]).
  4. Conclusion: After going through all dislikes pair without encountering a conflict, we can conclude that a bipartition is possible and return True.

This approach utilizes union-find's quick union and find operations to keep time complexity low, typically the near-constant time for each operation due to path compression, allowing efficient checks and unions while iterating through the dislikes array. Thus, the solution effectively groups individuals into two sets where disliked individuals are kept apart, which aligns with attempting to color a bipartite graph with two colors.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have n = 4 people, and the dislikes array is given as dislikes = [[1,2], [1,3], [2,4]]. Here's how the union-find approach would work on this input:

  1. Initialize Union-Find Structure: We start with a list p = [0, 1, 2, 3]. Each person is initially in their own separate group.

  2. Graph Construction: Construct the dislike graph g:

    1g = {
    2  0: [1, 2], // Person 1 dislikes 2 and 3.
    3  1: [0, 3], // Person 2 dislikes 1 and 4.
    4  2: [0],    // Person 3 dislikes 1.
    5  3: [1]     // Person 4 dislikes 2.
    6}

    Note that we have adjusted for 0-indexing by subtracting 1 from each person's label.

  3. Union-Find Algorithm: Now, we will proceed through each person and their dislikes:

    • Start with person 0; dislikes [1, 2].
      • For disliking person 1, since find(0) is 0 and find(1) is 1, there's no conflict. Union them by setting the representative or parent of dislikee 1 to the dislikee of person 0, which is p[find(1)] = find(0) resulting in p = [0, 0, 2, 3]. This effectively assigns person 2 and 1 to different groups.
      • For disliking person 2, find(0) is 0 and find(2) is 2. No conflict. Union again: p[find(2)] = find(0) leading to p = [0, 0, 0, 3].
    • Person 1; dislikes [0, 3].
      • Disliking person 0 doesn't need a union as it's already handled.
      • For disliking person 3, find(1) is 0 and find(3) is 3. No conflict. Union performed by p[find(3)] = find(1), leading to p = [0, 0, 0, 0]. However, given find(1) = 0, to union them correctly, we must set p[find(3)] = find(0) (person 1 dislikes first), but since p[3] is already 0 due to prior operations, no change occurs.
    • Person 2 and 3 do not need separate processing as their dislike relationships have already been handled.
  4. Conclusion: No conflict was found during the pairwise checks, indicating that we can successfully divide the four people into two groups despite their dislikes. For this particular small example, everyone ended up with the same root parent, but in a larger, more complex graph, the union-find algorithm would maintain separate roots where appropriate to reflect the correct bipartition into two groups.

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
5      
6        # Helper function to find the root of the set that element `x` belongs to.
7        def find_root(x):
8            if parent[x] != x:
9                # Path compression: make each looked-at node point to the root
10                parent[x] = find_root(parent[x])
11            return parent[x]
12
13        # Graph representation where key is a node and values are the nodes that are disliked by the key
14        graph = defaultdict(list)
15        for a, b in dislikes:
16            # Since people are numbered from 1 to N, normalize to 0 to N-1 for zero-indexed arrays
17            a, b = a - 1, b - 1
18            # Add each to the dislike list of the other
19            graph[a].append(b)
20            graph[b].append(a)
21      
22        # Initialize the parent array for disjoint-set union-find, each node is its own parent initially
23        parent = list(range(n))
24      
25        # Process every person
26        for i in range(n):
27            # Check dislikes for person `i`
28            for j in graph[i]:
29                # If person `i` and one of the people who dislike `i` has the same root, partition is not possible
30                if find_root(i) == find_root(j):
31                    return False
32                # Union operation: Connect the groups of the first disliked person to other disliked nodes' group
33                parent[find_root(j)] = find_root(graph[i][0])
34      
35        # If no conflicts found, partitioning is possible
36        return True
37

Java Solution

1class Solution {
2    private int[] parent; // array to store the parent of each node
3
4    // Function to check if it is possible to bipartition the graph based on dislikes
5    public boolean possibleBipartition(int n, int[][] dislikes) {
6        parent = new int[n];
7        List<Integer>[] graph = new List[n]; // adjacency list to represent the graph
8        Arrays.setAll(graph, k -> new ArrayList<>());
9        for (int i = 0; i < n; ++i) {
10            parent[i] = i; // initially, each node is its own parent
11        }
12        for (var edge : dislikes) {
13            int node1 = edge[0] - 1, node2 = edge[1] - 1; // adjusting index to be 0-based
14            graph[node1].add(node2);
15            graph[node2].add(node1); // since the graph is undirected, add edge in both directions
16        }
17        for (int i = 0; i < n; ++i) {
18            for (int adjacentNode : graph[i]) {
19                if (findParent(i) == findParent(adjacentNode)) {
20                    // If two adjacent nodes have the same set representative, bipartition isn't possible
21                    return false;
22                }
23                // Union the sets of the first neighbor of i and the current neighbor (j)
24                parent[findParent(adjacentNode)] = findParent(graph[i].get(0));
25            }
26        }
27        return true; // If no conflicts are found, bipartition is possible
28    }
29
30    // Function to find the representative (root parent) of a node using path compression
31    private int findParent(int node) {
32        if (parent[node] != node) {
33            parent[node] = findParent(parent[node]); // path compression for optimization
34        }
35        return parent[node];
36    }
37}
38

C++ Solution

1#include <vector>    // Required for using the vector type
2#include <numeric>   // Required for using the iota function
3#include <unordered_map> // Required for using unordered_map type
4#include <functional>   // Required for using std::function
5
6class Solution {
7public:
8    // Function to check if it is possible to bipartition the graph
9    bool possibleBipartition(int n, std::vector<std::vector<int>>& dislikes) {
10        // Initialize the parent vector and assign each node to be its own parent
11        std::vector<int> parent(n);
12        iota(parent.begin(), parent.end(), 0);
13      
14        // Create an adjacency list for the graph
15        std::unordered_map<int, std::vector<int>> graph;
16        for (const auto& edge : dislikes) {
17            int a = edge[0] - 1; // Adjusting index to be zero based
18            int b = edge[1] - 1; // Adjusting index to be zero based
19            graph[a].push_back(b); // Add b to a's dislike list
20            graph[b].push_back(a); // Add a to b's dislike list
21        }
22
23        // Define find function to find the set representative of a node
24        std::function<int(int)> find = [&](int node) -> int {
25            if (parent[node] != node) {
26                // Path compression: collapse the find-path by setting the parent
27                // of the intermediate nodes to the root node
28                parent[node] = find(parent[node]);
29            }
30            return parent[node];
31        };
32
33        // Iterate through each node to check for conflict in the bipartition
34        for (int i = 0; i < n; ++i) {
35            // If the node has dislikes
36            if (!graph[i].empty()) {
37                int parentI = find(i); // Find set representative of i
38                int firstDislike = graph[i][0]; // Get first element in dislikes list
39                for (int dislikeNode : graph[i]) {
40                    // If the set representative of i equals that of a dislike node,
41                    // the graph cannot be bipartitioned
42                    if (find(dislikeNode) == parentI) return false;
43                  
44                    // Union operation: set the parent of the set representative of the
45                    // current dislike node to be the set representative of the first dislike node
46                    parent[find(dislikeNode)] = find(firstDislike);
47                }
48            }
49        }
50
51        // If no conflicts are found, the graph can be bipartitioned
52        return true;
53    }
54};
55

Typescript Solution

1function possibleBipartition(n: number, dislikes: number[][]): boolean {
2    // Array to store the group color assignment for each person, initialized with 0 (no color).
3    const colors = new Array(n + 1).fill(0);
4
5    // Adjacency list to represent the graph of dislikes.
6    const graph = Array.from({ length: n + 1 }, () => []);
7
8    // Helper function to perform depth-first search for coloring and checking the graph.
9    // If a conflict is found, it returns true, indicating that the graph is not bipartite.
10    const depthFirstSearch = (person: number, colorValue: number): boolean => {
11        colors[person] = colorValue;
12        for (const neighbor of graph[person]) {
13            // If neighbor has the same color or if neighbor is uncolored but a conflict is detected upon coloring
14            if (colors[neighbor] === colors[person] || (colors[neighbor] === 0 && depthFirstSearch(neighbor, 3 ^ colorValue))) {
15                return true;
16            }
17        }
18        return false;
19    };
20
21    // Build the graph based on input dislike pairs.
22    for (const [a, b] of dislikes) {
23        graph[a].push(b);
24        graph[b].push(a);
25    }
26
27    // Attempt to color the graph using two colors (1 and 2), starting from each uncolored person.
28    // If a conflict arises during coloring, the graph cannot be bipartitioned, so return false.
29    for (let i = 1; i <= n; i++) {
30        if (colors[i] === 0 && depthFirstSearch(i, 1)) {
31            return false;
32        }
33    }
34
35    // If no conflicts were found, the graph can be bipartitioned, so return true.
36    return true;
37}
38

Time and Space Complexity

The given Python code is designed to determine if it is possible to bipartition a graph such that no two nodes that dislike each other are in the same group. Here is the analysis of its time and space complexity:

Time Complexity:

  • The program creates a graph g from the dislikes array. If there are E dislike pairs, this step has a time complexity of O(E) because it iterates through the dislikes array once.
  • The disjoint set function find has an amortized time complexity of O(alpha(N)) per call, where alpha is the inverse Ackermann function and is nearly constant (very slowly growing) for all practical values of N. This function is called up to 2E times—twice for each edge.
  • The outer for loop runs N times (once for each node), and the inner loop runs as many times as there are edges for a particular node. In the worst case, every node is connected to every other node, which would make this step take O(N^2). However, due to path compression in the find function, the complexity of the union find operation across all iterations is O(E * alpha(N)).
  • Combining these factors, the overall time complexity of the algorithm is O(E + E * alpha(N)) which simplifies to O(E * alpha(N)) since alpha(N) is nearly constant and not large.

Space Complexity:

  • There is a graph g which stores up to 2E edges in an adjacency list, so the space complexity for g is O(E).
  • The parent list p has a space complexity of O(N) because it stores a representative for each of the N nodes.
  • Ignoring the input dislikes, the auxiliary space used by the algorithm (the space exclusive of inputs) is O(N + E).
  • Therefore, the total space complexity of the function is O(N + E) taking into account the space for the graph and the disjoint set.

In summary, the time complexity is O(E * alpha(N)) and the space complexity is O(N + E).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫