并查集 先定义

int f[10100];//定义祖先

之后初始化

for(int i=1;i<=n;++i)
f[i]=i; //初始化

下面为并查集操作

int find(int x)//int 类型 查找
{
return f[x]==x?f[x]:f[x]=find(f[x]);//三目运算符查找
//如果f[x]==x 返回f[x] 否则返回f[x]=find(f[x]);
}
void unionn(int a,int b)//void 类型 连接
{
a=find(a),b=find(b);//查找两点的祖先，覆盖
f[b]=a;//更改祖先，连接两点
}

kruskal算法就是运用了并查集，但它真正耗时的地方是sort 排序

代码

1 #include
2 using namespace std;
3 struct edge
4 {
5 int u,v,w;//u起点 v 终点 w 边权 因为要排序，所以不需要nxt
6 bool operator <(const edge b) const//重载运算符，用于sort(可能更快，不确定)，不会，百度搜搜
7 {
8 return w<b.w;//小的在前
9 }
10 };
11 edge e[100010];//建边
12 int f[110];//记录每个点的祖先
13 int n,k,cnt,total,cot;//n 点数 k 关系数 cnt,cot 计数器 total 记录最小生成树的边权和
14 void add(int,int,int);//加边函数声明
15 int find(int);//并查集查找函数声明
16 void unionn(int,int);//并查集合并函数声明
17 int main()
18 {
19 scanf("%d%d",&n,&k);
20 for(int i=1;i<=n;++i) f[i]=i;//初始化
21 for(int u,v,w,i=1;i<=k;++i)
22 {
23 scanf("%d%d%d",&u,&v,&w);
24 add(u,v,w);//加边
25 add(v,u,w);//加边 无向图
26 }
27 sort(e+1,e+cnt+1);//排序 重载运算符排序
28 for(int i=1;i<=cnt;++i)//根据边权从小到大找边判断
29 {
30 int u=e[i].u,v=e[i].v,w=e[i].w;
31 if(find(u)!=find(v))//判断两点是否连接
32 {
33 total+=w;//记录边权和
34 unionn(u,v);//连接，避免后面循环误判
35 cot++;//记录找了几条边
36 }
37 if(cot==n-1) break;//找到n-1条边就退出
38 }
39 printf("%d",total);//输出
40 return 0;//结束
41 }
42 void add(int u,int v,int w)//建边
43 {
44 e[++cnt].u=u;
45 e[cnt].v=v;
46 e[cnt].w=w;
47 }
48 int find(int x)
49 {
50 return f[x]==x?f[x]:f[x]=find(f[x]);//三目运算符查找
51 }
52 void unionn(int a,int b)
53 {
54 a=find(a),b=find(b);
55 if(a!=b) f[b]=a;//加这个判断，有些题会在这里“做文章”
56 }