547 number of provinces

https://leetcode.com/problems/number-of-provinces/

Union find真的太香了

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int ans = n;
        int[] size = new int[n];
        int[] leader = new int[n];
        for (int i = 0; i < n; i++) {
            leader[i] = i;
            size[i] = 1;
        } 
        
        for (int i = 0; i + 1 < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    ans -= union(size, leader, i, j);
                }
            }
        }
        return ans;
    }
    private int union(int[] size, int[] leader, int a, int b) {
        int aleader = find(leader, a);
        int bleader = find(leader, b);
        
        if (aleader == bleader) {
            return 0;
        } else {
            if (size[aleader] >= size[bleader]) {
                size[aleader] += size[bleader];
                leader[bleader] = aleader;
            } else {
                size[bleader] += size[aleader];
                leader[aleader] = bleader;
            }
            return 1;
        }
    }
    private int find(int[] leader, int a) {
        if (leader[a] == a) {
            return a;
        }
        return leader[a] = find(leader, leader[a]);
    }
}