并查集理论基础用途用来快速判断两个元素是否处于同一集合原理定义一个一维数组fatherfather[i]表示i的上游元素。对于A,B,C如果三个元素处于同一集合那么他们是连通的可以记father[A] B, father[B] C, father[C] C.这样C就是他们的根。那么如何判断呢我们对目标元素分别向上查找根。如果查找到的根相同说明是同一个集合里。查找的过程类似树的叶子节点向上查找。为了优化我们进行路径压缩即在查找根的过程中对于一个集合中的任意元素ifather[i]的值都为同一个值便于查找。代码模板intn1005;// n根据题目中节点数量而定一般比节点数量大一点就好vectorintfathervectorint(n,0);// C里的一种数组结构// 并查集初始化voidinit(){for(inti0;in;i){father[i]i;//}}// 并查集里寻根的过程intfind(intu){returnufather[u]?u:father[u]find(father[u]);// 路径压缩}// 判断 u 和 v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}// 将v-u 这条边加入并查集voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}文章参考添加链接描述107 寻找存在路线题目链接添加链接描述思路使用并查集如果存在路径那么一定属于一个集合因为是无向图。#includeiostream#includevectorusingnamespacestd;intn;vectorintfathervectorint(110,0);intfind(intm){if(mfather[m])returnm;returnfather[m]find(father[m]);}voidjoin(intm,intn){mfind(m);nfind(n);if(mn)return;father[n]m;}boolisSame(intm,intn){mfind(m);nfind(n);returnmn;}intmain(){intn,m;cinnm;for(inti1;in;i){father[i]i;}ints,t;while(m--){cinst;join(s,t);}intsource,dest;cinsourcedest;if(isSame(source,dest)){cout1;}else{cout0;}return0;}