Count Unreachable Pairs of Nodes in an Undirected Graph

class DisjointSetUnion {
private:
    vector<int> parent, size;

public:
    DisjointSetUnion(int count) {
        parent.resize(count);
        size.resize(count, 0);
        for (int i = 0; i < count; i++) {
            parent[i] = i;
        }
    }
    int findParent(int node) {
        if (parent[node] != node) parent[node] = findParent(parent[node]);
        return parent[node];
    }
    void unite(int x, int y) {
        int rootX = findParent(x), rootY = findParent(y);
        if (rootX == rootY) {
            return;
        } else if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
        } else if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            size[rootX]++;
        }
    }
};

class Solution {
public:
    long long calculatePairs(int m, vector<vector<int>>& relations) {
        DisjointSetUnion dsu(m);
        for (auto relation : relations) {
            dsu.unite(relation[0], relation[1]);
        }
        unordered_map<int, int> clusterCount;
        for (int i = 0; i < m; i++) {
            clusterCount[dsu.findParent(i)]++;
        }

        long long paths = 0;
        long long leftoverNodes = m;
        for (auto cluster : clusterCount) {
            int countInCluster = cluster.second;
            paths += countInCluster * (leftoverNodes - countInCluster);
            leftoverNodes -= countInCluster;
        }
        return paths;
    }
};

This solution addresses the problem of counting unreachable pairs of nodes in an undirected graph using C++. The primary approach involves utilizing a Disjoint Set Union (DSU) data structure to manage and analyze node connectivity effectively.

• Start by defining a DisjointSetUnion class to encapsulate the union-find algorithm functionality:

  • Initialize each node to be its own parent and set an initial size.
  • Provide a method to find the representative parent for a given node, implementing path compression for efficiency.
  • Include a method to unite two nodes. This method links nodes by size, ensuring that smaller trees get attached under larger ones, maintaining a balanced tree structure.

• Implement the primary Solution class:

  • Define the calculatePairs function which uses instances of DisjointSetUnion.
  • Loop through given node relations and unite nodes according to provided edges.
  • Count the size of each cluster formed in the DSU by finding the parent for each node and accumulating the count in a hash map.
  • Calculate the number of unreachable pairs by examining the sizes of these clusters:
    • For each cluster, compute potential pair combinations with nodes not in the current cluster.
    • Subtract the nodes in the current cluster from the total to avoid recounting.

This approach ensures that each pair is considered exactly once, yielding an efficient solution to the problem. The DSU helps manage connected components and makes it feasible to total the unreachable pairs by systematically considering the contribution of each cluster independently.

class DisjointSet {
    int[] leader;
    int[] treeSize;
    public DisjointSet(int capacity) {
        leader = new int[capacity];
        for (int i = 0; i < capacity; i++)
            leader[i] = i;
        treeSize = new int[capacity];
    }
    public int findRoot(int node) {
        if (leader[node] != node)
            leader[node] = findRoot(leader[node]);
        return leader[node];
    }
    public void unite(int node1, int node2) {
        int root1 = findRoot(node1), root2 = findRoot(node2);
        if (root1 == root2) {
            return;
        } else if (treeSize[root1] < treeSize[root2]) {
            leader[root1] = root2;
        } else if (treeSize[root1] > treeSize[root2]) {
            leader[root2] = root1;
        } else {
            leader[root2] = root1;
            treeSize[root1]++;
        }
    }
}

class Solution {
    public long countPairs(int n, int[][] edges) {
        DisjointSet dsu = new DisjointSet(n);
        for(int[] edge: edges) {
            dsu.unite(edge[0], edge[1]);
        }

        Map<Integer, Integer> sizeMap = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int leader = dsu.findRoot(i);
            if(sizeMap.containsKey(leader)) {
                sizeMap.put(leader, sizeMap.get(leader) + 1);
            } else {
                sizeMap.put(leader, 1);
            }
        }
        
        long result = 0;
        long remainingNodes = n;
        for (int size : sizeMap.values()) {
            result += size * (remainingNodes - size);
            remainingNodes -= size;
        }
        return result;
    }
}

The provided Java code efficiently calculates the number of pairs of nodes in an undirected graph that are not reachable from each other. This method utilizes a DisjointSet (Union-Find) data structure to manage and merge sets of nodes, allowing it to keep track of which nodes are connected.

• The DisjointSet class manages the connectivity information:

  • It contains two arrays, leader and treeSize. The leader array keeps track of the root of each node, facilitating the path compression technique during the find operation, which helps in optimizing the union operation by attaching smaller trees under the root of the larger trees, stored in treeSize.
  • The findRoot function recursively finds the representative leader of a node, employing path compression for efficiency.
  • The unite function merges the sets containing two nodes. If the nodes are already in the same set, it does nothing; otherwise, it attaches the smaller tree under the larger tree, updating the tree size as necessary.

• The Solution class contains the method countPairs responsible for computing the count of unreachable pairs.

  • It initializes the DisjointSet with n nodes.
  • For each edge given, it merges the sets of the two connected nodes.
  • After all unions, it calculates the size of each connected component using a HashMap sizeMap.
  • To find the number of unreachable pairs, iterate through each component size. For each component, calculate the pairs that can be formed with nodes not in the current component and subtract these from the total count.

This approach minimizes direct combinatorial calculations for each node pair, leading to an efficient solution to the problem using graph theory and the Disjoint Set data structure. The result from the function represents the count of pairs that cannot communicate directly or indirectly through given edges.