Solution Explanation for LeetCode 886: Possible Bipartition

This problem asks whether a group of people can be partitioned into two groups such that no two people who dislike each other are in the same group. We can solve this using either Depth-First Search (DFS) or Union-Find.

Approach 1: Depth-First Search (DFS)

This approach uses a graph coloring algorithm. We represent the dislikes as an undirected graph where each person is a node, and an edge exists between two nodes if the corresponding people dislike each other. The goal is to color the graph with two colors (representing the two groups) such that no adjacent nodes have the same color.

Algorithm:

1. Build the graph: Create an adjacency list g representing the dislikes. Each index i in g corresponds to person i+1, and g[i] contains a list of people that person i+1 dislikes.

2. Color the graph: Use a Depth-First Search (DFS) function to color the graph. The dfs(i, c) function tries to color node i with color c (1 or 2). If it finds a conflict (a neighbor already has the same color), it returns False. Otherwise, it recursively colors its uncolored neighbors with the opposite color (3 - c).

3. Check for conflicts: Iterate through all nodes. If a node is uncolored, call dfs to color it. If dfs returns False, it means a conflict was found, and the bipartition is impossible.

Time Complexity: O(V + E), where V is the number of vertices (people) and E is the number of edges (dislikes). This is because DFS visits each vertex and edge once.

Space Complexity: O(V + E) for the adjacency list and the color array.

Approach 2: Union-Find

This approach uses the Union-Find data structure to determine if a bipartition is possible.

Algorithm:

1. Build the graph: Similar to the DFS approach, build an adjacency list representing the dislikes.

2. Union-Find operations: Initialize a parent array p for Union-Find. Initially, each person is in its own set (p[i] = i). Iterate through each person i. For each person j that i dislikes, check if i and j are already in the same set using the find(x) function. If they are, it means a bipartition is impossible because they are already in the same group. If they are not, unite their sets using p[find(j)] = find(g[i][0]), effectively assigning them to different groups.

3. Check for conflicts: If no conflicts are found during the Union-Find operations, a bipartition is possible.

Time Complexity: O(V + E * α(V)), where α(V) is the inverse Ackermann function, which is very small and can be considered practically constant. The Union-Find operations dominate the runtime.

Space Complexity: O(V) for the parent array p.

Code Examples (Python)

Approach 1 (DFS):

from collections import defaultdict
 
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g = defaultdict(list)
        color = [0] * n
        for u, v in dislikes:
            g[u - 1].append(v - 1)
            g[v - 1].append(u - 1)
 
        def dfs(node, c):
            color[node] = c
            for neighbor in g[node]:
                if color[neighbor] == c:
                    return False
                if color[neighbor] == 0 and not dfs(neighbor, 3 - c):
                    return False
            return True
 
        for i in range(n):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

Approach 2 (Union-Find):

from collections import defaultdict
 
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        parent = list(range(n))
        
        def find(i):
            if parent[i] == i:
                return i
            parent[i] = find(parent[i])
            return parent[i]
        
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
            return root_i != root_j
        
        g = defaultdict(list)
        for u, v in dislikes:
            g[u - 1].append(v - 1)
            g[v - 1].append(u - 1)
            
        for i in range(n):
            for neighbor in g[i]:
                if not union(i, neighbor):
                    return False
        return True
 

The provided code examples in other languages (Java, C++, Go, TypeScript, Rust) follow similar logic to the Python examples, adapting the syntax and data structures as needed for each language. They all implement either the DFS or Union-Find approach to solve the problem.