【LeetCode】LeetCode 547. 省份数量（Java版 什么是并查集）
【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();
}
}腾讯云开发者
