C/C++教程

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

本文主要是介绍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为根节点的树上。

 

这篇关于c/c++的小知识点：并查集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航