# 0547. Number of Provinces
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/number-of-provinces/
## h2
## Code

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