算法复习之并查集
标签：比较 oid init ++ for else iostream space pac
并查集是一种以树结构建立的能够高效处理分组问题中合并，查找操作的数据结构
支持三种基本操作：建立，查询，合并
实现：
1 #include 2 using namespace std;
3 const int maxn=10000;
4 int a[maxn],heigh[maxn],par[maxn];
5 void init(int n)
6 {
7 for(int i=0;i)
8 {
9 par[i]=i;
10 heigh[i]=1;
11 }
12 }
13 int findPar(int x)
14 {
15 if(x==par[x])
16 return x;
17 //递归求父亲，并直接连向根，路径压缩
18 else
19 return par[x]=fin(par[x]);
20 }
21 void connect(int x,int y)
22 {
23 x=findPar(x);
24 y=findPar(y);
25 if(x==y)
26 return ;
27 //如果父亲不相等，比较高度，合并
28 if(heigh[x]heigh[y])
29 {
30 par[x]=y;
31 }
32 else{
33 par[y]=x;
34 if(heigh[x]==heigh[y])
35 heigh[x]++;
36 }
37 }
算法复习之并查集
标签：比较 oid init ++ for else iostream space pac
原文地址：https://www.cnblogs.com/wtblogwt/p/9714865.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
算法复习之并查集
文章链接：http://soscw.com/essay/94641.html
评论