2316. Count Unreachable Pairs of Nodes in an Undirected Graph

T: O(n + e), e is edges len
S: O(n)

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

        Map<Integer, Integer> parentToComponentSize = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int parent = uf.find(i);
            parentToComponentSize.put(parent, parentToComponentSize.getOrDefault(parent, 0)+1);
        }

        long result = 0;
        long remainedSize = n;
        for (int size : parentToComponentSize.values()) {
            result += size * (remainedSize - size);
            remainedSize -= size;
        }
        return result;
    }
}

/**
4*3 = 12
1*2 = 2
2*0 = 0
 */

class UnionFind {
    int[] parent;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n ; i++) {
            parent[i] = i;
        }
    }
    public boolean union(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i != j) {
            parent[i] = j;
            return true;
        }
        return false;
    }

    public int find(int x) {
        if (parent[x] != x) { // find parent itself
            parent[x] = find(parent[x]);
        } 
        return parent[x];
    }
}

/**
use union find

T: O(n + e), e is edges len
S: O(n)
 */