【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