在学习krustra的算法时遇到了一个查找是否存在环路的算法,代码如下:
int find(int *parent,int f) { while(parent[f]>0) { f=parent[f]; } return f; } for(int i=0;i<k;i++) { int temp=0; int a,b; a=find(parent,Edge[i].begin); b=find(parent,Edge[i].end); if(a!=b)//无环 { parent[a]=b; sum+=Edge[i].weight; temp++; }
“被酒莫惊春睡重,赌书消得泼茶香,当时只道是寻常。”初见时仅仅是将它作为一个简单的递归转迭代的算法来看待,但之后再刷题时一而再再而三的遇上它,并且为它红了樱桃,却没能绿了芭蕉,经过查询方识卿之芳名------并查集:
是一种维护集合的数据结构,并查集三字分别取自:"Union","FInd",""Set'',初始化:
for(int i=1;i<=N;i++) { father[i]=i; }
FIND:
int findfather(int x) { while(father[x]!=x) { x=father[x]; } return x; }
Union:
void Union(int a,int b) { int m=findfather(a); int n=findfather(b); if(m!=n) { father[m]=n; }//反之,若相等则证明成环; } }
当然上述的算法时没有经过优化的,当元素成一条链式,一次向父节点进行查找会导致计算量过大,因而需要在find上做些手脚,即每一次查找完后,都让查找完的所有结点都指向统一的父节点,这样同一个集合中的查找就会缩短很多的时间:
Find:
int findfather(int x) { int a=x; while(x!=father[x]) { x=father[x]; } while(a!=father[a]) { int z=a; a=father[a]; father[z]=x;//将原先的根节点改为x; } }
这就是所谓的并查集算法;
举一道例题:
蓝桥杯和根植物:
问题描述
w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入格式
第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如:5 * 4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如:5 * 4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
这道题的实质即为求连通子集的个数,并查集AC;
AC代码:
#include<iostream> #include<string.h> using namespace std; int par[1000005]; int cnt; int n,m; int circle; int count; void init() { for(int i=1;i<=cnt;i++) { par[i]=i; } } int Find(int x) { int i=x; while(par[i]!=i) { i=par[i]; } int r=x; while(par[r]!=r) { int z=r; r=par[r]; par[z]=i; } return i; } void Union(int a,int b) { int m=Find(a); int n=Find(b); if(m!=n) { par[m]=n; } else { circle++; } } int main() { int u,v; cin>>m>>n; cnt=m*n; int k; cin>>k; init(); for(int i=1;i<=k;i++) { cin>>u>>v; Union(u,v); } for(int i=1;i<=cnt;i++) { if(par[i]==i) count++; } cout<<count<<endl; //cout<<circle<<endl;//多次一举,多输入个环的个数; }