并查集:
使用并查集可以把每个连通分量看作一个集合,该集合包含连通分量的所有点。这两两连通而具体的连通方式无关紧要,
就好比集合中的元素没有先后顺序之分,只有属于和不属于的区别。
#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;
}
相关文章
- Kruskal算法的C语言实现(并查集版)
- hdoj 4786 Fibonacci Tree【并查集+最小生成树(kruskal算法)】
- 最小生成树(Minimum Spanning Tree)——Prim算法与Kruskal算法+并查集
- hdu 1233(还是畅通project)(prime算法,克鲁斯卡尔算法)(并查集,最小生成树)
- 图的生成树(森林)(克鲁斯卡尔Kruskal算法和普里姆Prim算法)、以及并查集的使用
- CSP 地铁修建 Kruskal (最小生成树+并查集)
- 最小生成树kruskal算法并查集版 C语言实现
- 关于最小生成树(并查集)prime和kruskal
- 最小生成树kruskal算法并查集版 C语言实现
- 算法导论-用于不想交集合的数据结构(并查集)-kruskal最小生成树算法