【LeetCode】LeetCode 547. 省份数量（Java版 什么是并查集）

  📝个人主页：哈__

期待您的关注 

一、题目描述

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

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

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

返回矩阵中 省份 的数量。

二、思路讲解 

这是一道有关图的算法题目，题目当中给出了这样的描述：共有n个城市，其中的一些彼此相连，一些没有连接，如果a与b相连并且b与c相连，那么a与c也相连，这不就是连通性嘛。在看看这道题让求的是什么，求的是省份的数量，而一个省份内的地点之间都是连通的，题目让我们返回省份的值。我们的目标就是把每一个地区分到一个省份当中。

在这里我要给大家先讲解一种概念“并查集”。

什么是并查集？在我看来就是将图中的结点进行分类的操作，“并”就是将两个结点分类到一起，“查”就是查找结点到底是属于哪个类的。

这样子的描述不够清晰，我引入这样的一个例子。

我在以前看电视剧的时候，总是会有双方交战的场景，我当时就在想，他们的双方是如何分清谁是谁的，难道不会打错人吗？青青草原的绿草已经被羊羊们吃光了，羊羊们为了争夺资源开始了内战，在某一天喜羊羊带领着“喜门”大军去占领一片新的草原，沸羊羊带领着“沸门”大军也去争夺这片草原。两军在小路交叉口遇见。

 这次对决的双方羊数很多，假定羊都是白色的，无法区分，我们强制在两只羊交战之前都要自报家门，如果这两只羊是一个阵营的那么就不交战，那么该如何自报家门呢？乐羊羊问道：“你是哪一个阵营的，你阵营的首领是谁”。哈羊羊说道：“我是喜门的，我的首领是谁我忘了，不过我知道我的上层是谁，让我问问我的上层首领是谁”。于是哈羊羊问了他的上层，他的上层又问了上层，最后通知到了喜羊羊这里，喜羊羊又往下通报确认哈羊羊的身份，最后乐羊羊确认了哈羊羊的身份，并且把哈羊羊当作是自己人。

 喜羊羊和沸羊羊大战一场，突然一条情报传入到他们的耳中：“报告门主，美门门主美羊羊被灰太狼抓走了，请求支援！”喜羊羊和沸羊羊一听，立感不妙，现在不是内战的时候，要去救援美羊羊，为了防止内战，于是两羊商量，决定选出一羊作为另一只羊的上层，这样喜门和沸门就完成了合并过程，双方的羊在交战前再次询问上层的时候，都会是喜羊羊或者沸羊羊。

这就是一个简单的“查”和“并”的过程。并查集的关键就是这两个过程。

定义以下的find函数。p是一个数组，用于记录每一只羊的上层是谁。当一只羊的上层就是自己的时候，那这只羊就是门派老大。find函数用一句话来解释，就是查找一只羊的老大是谁。

int find(int x){
    while(p[x] != x){
       x = p[x];
    }
  return x;
}

定义以下的join函数，用于将两个元素归为一类。 也就是把两只羊归为一个阵营。

void join(int x,int y){
    int fx=find(x), fy=find(y);    //喜门1羊的老大是喜羊羊   沸门1号的老大是沸羊羊
    if(fx != fy)                // 如果他们的老大不同
        p[fx]=fy;            //把喜门1号的老大的老大改为沸羊羊 也就是喜羊羊的老大改为沸羊羊
}

 现在我们来解答题目。

class Solution {
    public int [] p = new int[201];
    public int find(int x){
       while(p[x] != x){
       x = p[x];
        }
    return x;
    }
    public void join(int x,int y){
        int px = find(x);
        int py = find(y);
        if(px != py){
            p[px] = py;
        }
    }
    public int findCircleNum(int[][] isConnected) {
        int m = isConnected.length;
        int n = isConnected[0].length;
        for(int i = 0;i<p.length;i++){
            p[i] = i;
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(isConnected[i][j] == 1 && i != j){
                    join(i,j);
                }
            }
        }
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0;i<m;i++){
            set.add(find(p[i]));
        }
        return set.size();
    }
}

上边用到了HashSet结构，HashSet结构不允许有重复值，对于我们的p数组，我们去查找每一个人的门主是谁然后把门主添加到set中，最后进行一个去重，剩下来的就是门主的个数，他们无法合并到一起。对于题目来说就是省份的个数。题目中只有connected为1的两个城市，我们进行join操作。

可见效率有多低。 

三、优化find方法

我们之前的找老大的方法是层层向上，但是想一想，一个门派的所有老大只有一只羊，如果我们把每只羊的上层都直接改为门主的话，这样不需要在层层的往上找，是不是就十分的方便了呢？（喜羊羊和沸羊羊都是无限体力的工作机器）

int find(int x){
    //如果x的上层不是门主，那么就接着查找这个人上层的老大
    if(p[x] != x) p[x] = find(p[x]); //查找老大的时候顺便将这个人的上层直接修改为门主
    return p[x];
}

 再来看看结果。

 代码。

class Solution {
    public int [] p = new int[201];
    public int find(int x){
       if(p[x] != x) p[x] = find(p[x]); //查找老大的时候顺便将这个人的上层的老大全部修改为门主
        return p[x];
    }
    public void join(int x,int y){
        int px = find(x);
        int py = find(y);
        if(px != py){
            p[px] = py;
        }
    }
    public int findCircleNum(int[][] isConnected) {
        int m = isConnected.length;
        int n = isConnected[0].length;
        for(int i = 0;i<p.length;i++){
            p[i] = i;
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(isConnected[i][j] == 1 && i != j){
                    join(i,j);
                }
            }
        }
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0;i<m;i++){
            set.add(find(p[i]));
        }
        return set.size();
    }
}