c/c++的小知识点:并查集

在朋友圈、旅游线路等问题中均使用到并查集的概念,在数据结构中讲过这个知识点

 相关题目:

1.旅行路线规划

PTA | 程序设计类实验辅助教学平台

2.朋友圈

PTA | 程序设计类实验辅助教学平台

并查集有两个基本操作

1.find:查找元素所属子集

2.union:合并两个子集为一个新的集合

并查集的基本结构:树

不同的树就是不同的集合,树的集合是森林,所以并查集属于森林

对于Find操作,代码非常简单

int find(int x)
{
    return parent[x] == x ? x : find(parent[x]);
}

该代码比较元素x的父节点parent[x]是否等于x自身,如果是便说明找到了根节点(根节点的父节点是自身),直接返回;否则,把x的父节点parent[x]传入find,直到找到根节点。


下面是union操作

void to_union(int x1, int x2) 
{
    int p1 = find(x1);
    int p2 = find(x2);
    parent[p1] = p2;
}

传入两个元素,分别找到根节点,使根节点p1的父节点为p2,即将p1为根节点的这棵树合并到p2为根节点的树上。

 

上一篇:houseoforange_hitcon_2016 House of orange


下一篇:pwny