剑指offer116：省份数量

题目：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

示例一：

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

输出：2

示例二：

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

输出：3

分析：
第一种解法：
图的搜索算法可以用来计算图中的子图的数目。扫描图中所以的节点。如果某个节点v之前没有访问过就搜素它所在的子图，当所有节点都访问完之后就可以知道图中有多少个子图了。
广度优先搜索和深度优先搜索都可以用来计算图中子图的数目，该题以广度优先遍历为例。
如果某个城市i对应的节点之前没有访问过，则调用函数findCircle访问他所在城市圈对应子图的所有节点，变量result记录城市圈的数目，每访问一个朋友圈对应的子图，result就加1。
如果有n个城市，那么图中有n个节点和O（n ^2）条边，广度优先搜索的时间复杂度是O（n ^2）。
第二种解法：
应用并查集解决问题。（具体操作见注释）
创建长度为n的数组fathers存储n个节点的父节点，有了这个数组fathers，如果想知道节点i所在的子集的根节点就可以从节点i开始沿着指向父节点的指针搜索，时间复杂度看起来是O（n），但可以将从节点i到根节点的路径压缩，从而优化时间效率。

代码：

package com.kuang;

import sun.java2d.opengl.OGLRenderQueue;

import java.util.LinkedList;
import java.util.Queue;

public class FindCircleNum {
    public int findCircleNum1(int[][] isConnected) {
        boolean[] visited = new boolean[isConnected.length];
        int result = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]){
                findCircle(isConnected,visited,i);
                result++;
            }
        }
        return result;
    }

    private void findCircle(int[][] isConnected, boolean[] visited, int i) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        visited[i] = true;
        while (!queue.isEmpty()){
            int t = queue.remove();
            for (int friend = 0; friend < isConnected.length; friend++) {
               if (isConnected[t][friend]==1 && !visited[friend]){
                   queue.add(friend);
                   visited[friend] = true;
               }
            }
        }
    }
}

package com.kuang;

public class FindCircleNum2 {
    public int findCircleNum(int[][] M){
//        数组fathers用来记录每个节点的根节点，如果班级中有n个学生，那么n个节点被初始化
//        为n个互不连通的子图，在并查集中每个节点的父节点指针都指向自己
        int[] fathers = new int[M.length];
        for (int i = 0; i < fathers.length; i++) {
            fathers[i] = i;
        }
        int count = M.length;
        for (int i = 0; i < M.length; i++) {
            for (int j = i+1; j < M.length; j++) {
//                i，j互为朋友，调用union在必要时合并他们的圈
                if (M[i][j] ==1 && union(fathers,i,j)){
//                    每当两个子集合并成一个子集，子集数目减1，相应地朋友圈也减1
                    count--;
                }
            }
        }
        return count;
    }
    private boolean union(int[] fathers,int i, int j){
        int fatherOfI = findFather(fathers,i);
        int fatherOfJ = findFather(fathers,j);
//        判断节点i和节点j的根节点是否相同
        if (fatherOfI != fatherOfJ){
//            如果把fathers[i]设为j，就相当于把整个第一个子图挂在节点j下，也就是合并两个子图
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }
//        节点i和节点j根节点相同，它们已经位于同一个子集中，那么它们对应的两个学生已经在同一个圈里了，
//        也就没必要合并，此时直接返回false
        return false;
    }
//用来查找一个节点的根节点，一旦得知节点i的根节点就记录到father[i]中，就相当于压缩了路径
    private int findFather(int[] fathers, int i) {
        if (fathers[i] != i){
            fathers[i] = findFather(fathers,fathers[i]);
        }
        return fathers[i];
    }
}