disjoint set - union find

use class

class Solution {
    public int findCircleNum(int[][] isConnected) {
        
        int n = isConnected.length;
        DSU dsu = new DSU(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    dsu.union(i, j);
                }
            }
        }
        return dsu.res;
    }
    
    class DSU {
        int roots[];
        int res;
        DSU(int n) {
            roots = new int[n];
            res = n;
            for (int i = 0 ; i < n; i++) {
                roots[i] = i;
            }
        }
        
        private void union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                roots[x] = y;
                res--;
            }
            
        }
        
        private int find(int x) {
            if (roots[x] != x) {
                roots[x] = find(roots[x]); // 會有 path compression 的效果
            }
            return roots[x];
        }
    }
}

    // init
    int[] roots = new int[n];
    for (int i = 0; i < n; i++) {
        roots[i] = i;
    }
    
    // normal
    private void union(int roots[], int i , int j) {
        int x = find(roots, i);
        int y = find(roots, j);
        if (x == y) return;
        roots[x] = y;
    }
    
    // for some question
    private int union(int roots[], int i , int j, int res) {
        int x = find(roots, i);
        int y = find(roots, j);
        if (x == y) return;
        if (x != y) {
            roots[x] = y;
            res--; // depends on question
        }
        return res; // depends on question
    }

    private int find(int roots[], int i) {
        while (roots[i] != i) {
            roots[i] = roots[roots[i]]; // add path compression
            i = roots[i];
        }
        return i;
    }