题目描述（传送门）

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
 

解题思路&代码实现

这道题类似于：【每日一题】牛客：计算朋友圈（并查集练习01）
知识点：【高阶数据结构】并查集详解

/**
 * @ClassName lk547
 * @Description ：TODO
 * @Author Josvin
 * @Date 2021/01/16/12:01
 */
public class lk547 {
    private static int count;
    private static int[] id;
    private static int[] size;
    public int findCircleNum(int[][] isConnected) {
        Union_Find(isConnected);
        return count;
    }

    private void Union_Find(int[][] isConnected) {
        int N = isConnected.length;
        id = new int[N];
        size = new int[N];
        count = N;
        for (int i = 0; i < N; i++) {
            id[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (1 == isConnected[i][j]) {
                    Union(i, j);
                }
            }
        }
    }

    private static void Union(int p, int q) {
        int proot = Find(p);
        int qroot = Find(q);
        if (proot == qroot) {
            return;
        }
        if (size[p] > size[q]) {
            id[proot] = qroot;
            size[qroot] += size[p];

        } else {
            id[qroot] = proot;
            size[proot] += size[q];
        }
        count--;
    }

    private static int Find(int p) {
        if (id[p] != p) {
            id[p] = Find(id[p]);
        }
        return id[p];
    }
}