专栏首页专注研发最小生成数(并查集)Kruskal算法

最小生成数(并查集)Kruskal算法

并查集:
使用并查集可以把每个连通分量看作一个集合,该集合包含连通分量的所有点。这两两连通而具体的连通方式无关紧要,
就好比集合中的元素没有先后顺序之分,只有属于和不属于的区别。
#define N 100
int father[N];
void init()
{
for(int i=0;i<n;i++)
father[i]=1;
}
void union(int x,int  y)     //合并两元素所在集合
{
x=getfather(x);
y=getfather(y);
if(x!=y)
father[x]=y;

}
/*bool same(int x,int y)     //判断两元素在不在同一集合
{return getfather(x)==getfather(y);}
*/
int getfather(int x)   //获得该元素的父亲节点
{
while(x!=father[x])
{x=father[x];}
return x;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • poj 3620

          如果一个潮湿的格子的相邻的四个方向有格子也是潮湿的,那么它们就可以构成更大

    瑾诺学长
  • POJ 2531

    瑾诺学长
  • poj 1562 dfs

    瑾诺学长
  • cf1051F. The Shortest Statement(最短路)

    由于边数的限制,非树边连接的点不会超过$2*(m - (n - 1)) = 42$个

    attack
  • poj1251 Jungle Roads Kruskal算法+并查集

    风骨散人Chiam
  • 洛谷P2770 航空路线问题(费用流)

    为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边

    attack
  • Codeforces Round 767C 树形结构求子树和

    很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就sz重置成0.

    用户2965768
  • 强连通专题

    求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> ...

    用户1624346
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • POJ 刷题系列:2993. Emag eht htiw Em Pleh

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券