并查集代码java,并查集代码路径压缩

如何在并查集问题上求出集合的数量

并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。

并查集的主要操作有

1－合并两个不相交集合 Union(A,B)

2－判断两个元素是否属于同一个集合 FindSet(X)

建立每个元素到父亲指针，初始时父亲指针指向本身。(F[X]:=X)

当然也可以令它等于-1或高度、大小的相反数，便于以后的优化

则Find过程为：

//pascal

Function Find(X:Integer):Integer;

Begin

If  F[X]X Then Return Find(F[X]) Else Return X;

End;

Procedure Union(A,B:Integer):Integer;

Begin

F[Find(A)]:=F[Find(B)];

End;

//c

int find(int x)

{

if(f[x]!=x)return(find(f[x]);

else

return(x);

}

void union(int a,int b)

{

f[find(a)]=f[find(b)];

}

同BST一样，最坏情况为一条链，那么进行一次Find操作的时间复杂度为O(N)，代价太大。

启发式合并

2.路径压缩

启发式合并

思想很简单，将结点少的树合并到结点多的树上,也可以把高度小的数合并到高度大的树上，其中后者与路径压缩会有少许冲突。

路径压缩

思想也很简单，当一条路找到根结点了以后，把所有处于路径中的结点的父亲指针直接指向该集合的父亲。

路径压缩以后的程序

Procedure Find(X:Integer):Integer;

Begin

If F[X]X Then F[X]:=Find(F[X]);

Return F[X];

End;

int find(int x)

{

if(f[x]==x)return(x);

return(f[x]=find(f[x]));

}

union的代码稍长，就省略了

LeetCode 力扣官方题解 - 1020. 飞地的数量

题目描述

给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

示例 2：

提示：

根据飞地的定义，如果从一个陆地单元格出发无法移动到网格边界，则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类：第一类陆地单元格和网格边界相连，这些陆地单元格不是飞地；第二类陆地单元格不和网格边界相连，这些陆地单元格是飞地。

我们可以从网格边界上的每个陆地单元格开始深度优先搜索，遍历完边界之后，所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格的边界相连，是飞地。

代码实现时，由于网格边界上的单元格一定不是飞地，因此遍历网格统计飞地的数量时只需要遍历不在网格边界上的单元格。

代码

Java

C#

C++

C

Python3

Golang

JavaScript

复杂度分析

也可以通过广度优先搜索判断每个陆地单元格是否和网格边界相连。

首先从网格边界上的每个陆地单元格开始广度优先搜索，访问所有和网格边界相连的陆地单元格，然后遍历整个网格，统计飞地的数量。

代码

Java

C#

C++

C

Python3

Golang

JavaScript

复杂度分析

除了深度优先搜索和广度优先搜索的方法以外，也可以使用并查集判断每个陆地单元格是否和网格边界相连。

并查集的核心思想是计算网格中的每个陆地单元格所在的连通分量。对于网格边界上的每个陆地单元格，其所在的连通分量中的所有陆地单元格都不是飞地。如果一个陆地单元格所在的连通分量不同于任何一个网格边界上的陆地单元格所在的连通分量，则该陆地单元格是飞地。

并查集的做法是，遍历整个网格，对于网格中的每个陆地单元格，将其与所有相邻的陆地单元格做合并操作。由于需要判断每个陆地单元格所在的连通分量是否和网格边界相连，因此并查集还需要记录每个单元格是否和网格边界相连的信息，在合并操作时更新该信息。

在遍历网格完成并查集的合并操作之后，再次遍历整个网格，通过并查集中的信息判断每个陆地单元格是否和网格边界相连，统计飞地的数量。

代码

Java

C#

C++

C

Python3

Golang

JavaScript

复杂度分析

BY /

本文作者：力扣

判断图中两点是否相通 java

目测很像朋友圈问题啊，首先数据结构有Point(x,y),line(Point a,Point b)，应该是已知一些点，和一些线，若点A可通过一条或多条线到点B，则认为A、B连通，可用并查集解决，百度一下即可，应该是最后判断set(a)==set(b)则两点连通

ACM 1233 还是畅通工程，我用的是并查集的思路，其中排序用的冒泡，提交显示超时，求指导，问题出在哪

冒泡排序的时间复杂度是o(n^2)，但是这个n指的是待排序的元素数量，这题里输入的点数是n，边数是n(n-1)/2，也就是n^2级别的边数，你这里要排序的是边，所以你用冒泡的时间复杂度就是o((n^2)^2)=o(n^4)，这题n是100，n^4=10亿，一般OJ上1亿级别的复杂度就要跑接近1秒，你这单组数据就10亿，更别说题目还是多组数据，必然超时。这题要排序边的话必须要用o(nlogn)复杂度的排序，比如快速排序、堆排序和归并排序。

另外，除开排序，你这代码本身逻辑也有问题啊，你试一下这组数据：

4

1 2 1

1 3 7

1 4 8

2 3 9

2 4 7

3 4 1

答案应该是9。

你说用到并查集，我完全没看到并查集在哪里啊，这题就是个完全图的最小生成树，用prim算法会好一点，用kruskal算法的话并查集部分还要加上路径压缩才不会超时。你这里的town数组其实只有等于node和不等于node两种状态是有用的，node的值又不会变，这和boolean数组没什么实质的区别，这就是个标记数组，而不是并查集。

并查集POJ1988为什么WA？

错误在于那个count数组

你的count数组并不能正确的记录i上面有多少个,因为在一次移动后,你只更新了b的count值,但其实y以及原来就在y上面的那些的count值都需要更新.

如:

3

M 2 3

M 1 2

C 3

你的程序会打出1,但很明显是0.

如果你强行更新count的值肯定会超时了...而且你find的时没用路径压缩也很可能会超时....

我建议你就记录每个i到root[i]之间有好多个,再记录每一叠最上面的是什么,然后就都是并查集的基本操作了...我附个程序吧(已AC):

#includestdio.h

const char inf[]="POJ1988.in";

const char ouf[]="POJ1988.out";

const long maxn=30000;

long P;

long root[maxn+10];

long count[maxn+10];

long top[maxn+10];

void prepare(){

long i;

for(i=1;i=maxn;i++){

root[i]=0;

count[i]=0;

top[i]=i;

}

}

long find(long x,long tot){

long pre;

tot=0;

if(!root[x])return x;

pre=x;tot+=count[x];x=root[x];

while(root[x]){

count[pre]+=count[x];

root[pre]=root[x];

pre=x;

tot+=count[x];

x=root[x];

}

return x;

}

void combine(long a,long b){

root[a]=top[b];

count[a]=1;

top[b]=top[a];

}

void solve(){

long i,ans,x,y,rx,ry;

char order;

scanf("%ld",P);

for(i=1;i=P;i++){

scanf("%c",order);

scanf("%c",order);

if(order=='M'){

scanf("%ld%ld",x,y);

rx=find(x,ans);

ry=find(y,ans);

combine(rx,ry);

}else{

scanf("%ld",x);

rx=find(x,ans);

printf("%ld\n",ans);

}

}

}

main(){

//freopen(inf,"r",stdin);

//freopen(ouf,"w",stdout);

prepare();

solve();

return 0;

}