并查集模拟数组实现C++

C语言数组模拟实现的并查集算法,功能是将输入的已经确定属于一个集合的顶点u v合并到一个集合,便于后续的查询,当然查询之后也可以再输入确定的属于一个集合的u v顶点,再做查询。主要思想是对输入的v u顶点做判断,如果他们没有共同的父亲顶点,那么就把v的父亲设置为u。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int setNum[100];
void initSet(int n){
for(int i=1;i<=n;i++) setNum[i]=i;
}
int getParent(int v){
if(setNum[v]==v) return v;
setNum[v]=getParent(setNum[v]);
return setNum[v];
}
void andSet(int v,int u){
int t1=getParent(v);
int t2=getParent(u);
if(t1!=t2) setNum[t2]=t1;
}
int main(){
ios::sync_with_stdio(false);
int n,m; // n为顶点个数,m为边的条数
n=10; m=9;
initSet(n); //初始化集合关系
int edge[9][2]={1,2, 3,4 ,5,2 ,4,6 ,2,6 ,8,7 ,9,7 ,1,6 ,2,4};
for(int i=0;i<m;i++) andSet(edge[i][0],edge[i][1]);
for(int i=0;i<n;i++) if(setNum[i]==i+1) cout<<i+1<<endl;
return 0;
}