并查集用于检测环路
发布时间
阅读量：
阅读量
并查集是一种广泛应用的数据结构类型。该算法用于将数据按照特定规则归类形成集合体。这些集合通常呈现出明显的层级结构，并以根节点为基础进行区分。其中每个集合都通过根节点来与其他集合区分开来。其核心功能包括快速查找和合并两个元素所在的集合。
//查找
int find(int x)
{
int r=x;
while(pre[r]!=r)
r=pre[r];//找到他的前导结点
int i=x,j;
while(i!=r)//路径压缩算法
{
j=pre[i];//记录x的前导结点
pre[i]=r;//将i的前导结点设置为r根节点
i=j;
}
return r;
}
//合并
void UnionSet(int x, int y){
int xp = find(x);
int yp = find(y);
pre[xp] = yp;
}代码虽然不复杂但其主要目标在于通过构建森林结构将分散的数据整合成一个统一的集合在
全部评论 (0)
还没有任何评论哟~