Possible Bipartition

class DisjointSet {
private:
    vector<int> root, size;

public:
    DisjointSet(int count) {
        root.resize(count);
        size.resize(count, 0);

        for (int i = 0; i < count; i++) {
            root[i] = i;
        }
    }

    int findRoot(int z) {
        if (root[z] != z) root[z] = findRoot(root[z]);
        return root[z];
    }

    void merge(int u, int v) {
        int rootU = findRoot(u), rootV = findRoot(v);
        if (rootU == rootV) {
            return;
        } else if (size[rootU] < size[rootV]) {
            root[rootU] = rootV;
        } else if (size[rootU] > size[rootV]) {
            root[rootV] = rootU;
        } else {
            root[rootV] = rootU;
            size[rootU]++;
        }
    }
};

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(n + 1);
        for (auto& pair : dislikes) {
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }

        DisjointSet dsu(n + 1);
        for (int node = 1; node <= n; node++) {
            for (int adjacent : graph[node]) {
                if (dsu.findRoot(node) == dsu.findRoot(adjacent)) return false;
                dsu.merge(graph[node][0], adjacent);
            }
        }
        return true;
    }
};

The given C++ solution tackles the problem of determining if a possible bipartition exists within a set of dislikes among n people. It utilizes a Disjoint Set Union (DSU) data structure for efficient union and find operations.

• The DisjointSet class provides functionality to manage and merge sets, and to find the root of elements efficiently using path compression.

• In the possibleBipartition member function of the Solution class, a graph is first constructed where each person (node) has edges to the person they dislike, forming an adjacency list.

• The DisjointSet object, dsu, is initialized to manage sets ranging from 1 through n.

• The solution iterates over each node and checks if the current node has the same root as any of its adjacent nodes (indicating them being in the same set, which should not happen in a bipartite graph). If they share the same root, the function returns false.

• If not, the algorithm attempts to merge the first disliked person (from the adjacency list of the current person) with other disliked persons from the list to make sure they are all grouped in alternate partitions.

• If no conflicts are found throughout the iterations, the function returns true indicating the graph can be bipartitioned.

class DisjointSet {
    int[] leader;
    int[] depth;

    public DisjointSet(int capacity) {
        leader = new int[capacity];
        for (int i = 0; i < capacity; i++)
            leader[i] = i;
        depth = new int[capacity];
    }

    public int locate(int x) {
        if (leader[x] != x)
            leader[x] = locate(leader[x]);
        return leader[x];
    }

    public void connect(int x, int y) {
        int rootX = locate(x), rootY = locate(y);
        if (rootX == rootY) {
            return;
        } else if (depth[rootX] < depth[rootY]) {
            leader[rootX] = rootY;
        } else if (depth[rootX] > depth[rootY]) {
            leader[rootY] = rootX;
        } else {
            leader[rootY] = rootX;
            depth[rootX]++;
        }
    }
}

class BipartiteChecker {
    public boolean canPartition(int n, int[][] dislikes) {
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
        for (int[] pair : dislikes) {
            int one = pair[0], two = pair[1];
            adjacencyList.computeIfAbsent(one, k -> new ArrayList<Integer>()).add(two);
            adjacencyList.computeIfAbsent(two, k -> new ArrayList<Integer>()).add(one);
        }

        DisjointSet dsu = new DisjointSet(n + 1);
        for (int person = 1; person <= n; person++) {
            if (!adjacencyList.containsKey(person))
                continue;
            for (int adjacent : adjacencyList.get(person)) {
                // Check if currently considered person and the adjacent person are in the same set.
                if (dsu.locate(person) == dsu.locate(adjacent))
                    return false;
                // Unify all neighbors of a person to the first neighbor in the list.
                dsu.connect(adjacencyList.get(person).get(0), adjacent);
            }
        }
        return true;
    }
}

This solution involves a strategy to determine whether it's possible to divide a set of individuals into two separate groups such that no two individuals in the same group dislike each other. The implementation uses Java and applies a union-find or disjoint set data structure for efficient group management and relationship checks.

• Initiate a DisjointSet class that maintains two arrays: leader, which stores the leader for each element, ensuring path compression during the find operation, and depth, which helps in optimizing union operations by tracking the depth or rank of each set.
• Provide methods locate to find the root leader of any element, compressing the path, and connect to unite two elements by rank, maintaining a balanced tree structure.
• Implement the BipartiteChecker class, specifically the canPartition method:
  1. Create an adjacency list from the dislikes input to facilitate easy and quick access to each person's disliked individuals.
  2. Initialize the DisjointSet with a capacity of n+1 to handle 1-based indexing conveniently.
  3. For each person, omit processing if there are no recorded dislikes.
  4. Process each disliked relationship:
     • Verify if two individuals currently being checked are in the respective same set using the locate method. If true, it implies that creating two groups where no individuals in the same group dislike each other is impossible, hence returning false.
     • For adjacency manipulations, link all neighbors of a person to the first neighbor using the connect method.
  5. If all checks and connections are processed without conflicts, return true, confirming that a bipartition is possible.

This structured approach ensures that the relationship between disliked pairs is managed efficiently, leveraging union-find operations to ascertain group conflicts swiftly. The solution effectively identifies if a possible bipartition can be made based on the given dislikes relationship matrix.

class DisjointSet:
    def __init__(self, n):
        self.root = list(range(n))
        self.height = [0] * n

    def locate(self, p):
        if self.root[p] != p:
            self.root[p] = self.locate(self.root[p])
        return self.root[p]

    def connect(self, u, v):
        root_u = self.locate(u)
        root_v = self.locate(v)

        if root_u == root_v:
            return

        if self.height[root_u] < self.height[root_v]:
            self.root[root_u] = root_v
        elif self.height[root_u] > self.height[root_v]:
            self.root[root_v] = root_u
        else:
            self.root[root_v] = root_u
            self.height[root_u] += 1

class BipartitionChecker:
    def canBipartition(self, total: int, dislikePairs: List[List[int]]) -> bool:
        graph = [[] for _ in range(total + 1)]
        for pair in dislikePairs:
            graph[pair[0]].append(pair[1])
            graph[pair[1]].append(pair[0])

        ds = DisjointSet(total + 1)
        for vertex in range(1, total + 1):
            if len(graph[vertex]) == 0:
                continue
            base = graph[vertex][0]
            for disliked in graph[vertex]:
                if ds.locate(vertex) == ds.locate(disliked):
                    return False
                ds.connect(base, disliked)

        return True

The provided Python script is designed to check if a bipartition of a graph is possible, given a list of pairs representing nodes that dislike each other. This is implemented using a Disjoint Set (Union-Find) data structure enhanced with path compression and union by rank to efficiently manage node connections and determine the root of each node.

Here is a detailed breakdown of the implementation:

• DisjointSet Class

  • Initializes with each node as its root and height initialized to zero.
  • locate method implements path compression technique to find the root of a node and compresses the path along the way for efficiency.
  • connect method joins two subsets based on the rank (height), which helps keep the tree shallow.

• BipartitionChecker Class

  • canBipartition checks if the graph can be divided into two groups such that no two nodes within the same group are in the dislike pair:
    • It creates the graph as an adjacency list and initializes the Disjoint Set for the nodes.
    • Iterates through each vertex, checking connectivity within its dislike group using the DisjointSet methods.
    • If ever a node and one of its disliked nodes are found to have the same root, the method returns False, indicating that a bipartition is not possible.
    • If all checks pass without conflicts, the method returns True, indicating that a bipartition is possible.

This approach effectively segments the graph while maintaining a check for cycles within any segment which would violate the bipartition conditions.