并查集(C)

张开发
• 2026/4/18 15:43:25 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

并查集(C)
1. 概论定义并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题即所谓的并、查。比如说我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。主要构成并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。数组 f[ ] 记录了每个点的前驱节点是谁函数 find(x) 用于查找指定节点 x 属于哪个集合函数 join(x,y) 用于合并两个节点 x 和 y 。作用并查集的主要作用是求连通分支数如果一个图中所有点都存在可达关系直接或间接相连则此图的连通分支数为1如果此图有两大子图各自全部可达则此图的连通分支数为2……2.概念如上我以百度之星上的一道题目为例给大家演示下代码如何写Dev-c我直接给大家代码吧#includebits/stdc.h using namespace std; const int N10005; int f[N];//存当前节点的父节点编号 int n; //初始化将自己设为自己的父节点 void init(){ for(int i1;iN;i){ f[i]i; } } //查找到根节点就是查到最顶层查不了为止 //我列举了两种书写代码形式一个意思 //int find(int x){ // if(xf[x]){ // return x; // }else{ // return f[x]find(f[x]); // } //} int find(int x){ return xf[x]?x:f[x]find(f[x]); } //添加关系 void join(int x,int y){ int ifind(x); int jfind(y); f[i]j; // f[j]i;任意那种都行 } int main(){ cinn; init();//记得调用啊我经常忘记调用 while(n--){ int a,b; cinab; join(a,b); } int q; cinq; while(q--){ int a,b; cinab; if(find(a)find(b)){ cout1endl; }else{ cout0endl; } } return 0; }测试用例5 1 2 2 3 1 7 4 5 5 6 2 2 7 1 4运行结果这段代码执行完后由于这个测试用例最大的数为7因此我只展示了f数组前十个元素如下感谢大家浏览

更多文章