标题并查集的查询与合并详解 作者Ggggggtm 寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景一、并查集的概念并查集是一种树形的数据结构。使用树型结构来存储数据。树根的编号即为整个树的标号且每个节点存储的数据是他的父节点下标。并查集被很多OIer认为是最简洁而优雅的数据结构之一主要用于解决一些元素分组的问题。它管理一系列不相交的集合并支持两种操作合并Union把两个不相交的集合合并为一个集合。查询Find查询两个元素是否在同一个集合中。二、并查集的实现1.并查集不同集合(树)的形成我们把并查集不同集合树的实现主要分为以下几个点我们先给出n个数据把n个数据存储到不同的集合当中p[ i ] i在这里我们把每个p[ i ]分别看成一个不同集合也就是一棵树。p[ i ] ii即为这棵树的编号这颗树下面的孩子节点存储的数据是父节点的下标。当p[ i]i 时就相当于找到了根节点。我们刚开始每个集合中的元素只有一个。后续合并后集合元素个数不断增加。2.find()函数找一个元素集合的编号元素所属于树的祖宗我们查找一个元素的集合把元素的当作下标传给find()函数代码如下12345678intfind(intx){if(p[x]!x){p[x]find(p[x]);}returnp[x];}我们p[x]中存储的正是他的父节点从而就可以一直往上查找直到p[ x ]x时结束。当p[ x ]x时就相当于找到了根节点。此时的p[ x ]存储的是这棵树的编号。我这发现刚开始每个集合当中都只有一个元素也就是p[ x ]后面我们会对不同的集合进行合并使得一个集合有多个元素。我们再找祖宗节点时进行了路径压缩。什么是路径压缩呢路径压缩就是我们在查找某个元素的祖宗时在找父节点的这条路经上的元素都指向祖宗节点以便于我们后面的查找的时间复杂度近乎O1。3.合并两个不同集合(合并两棵不同的树)我们直到了每棵树的根节点存储的是这个树的编号而不是父节点。当我们要合并两颗树时我们只需要把一棵树的根节点存储的编号改为另一棵树的根节点编号。简单的理解就是一个树的根节不再是根节点而是一个子节点该树的根节点存储的也不再是编号而是存储的父节点该父节点就是另一棵树的根节点。我们看代码12//合并 把a的祖宗节点的父节点当作b的祖宗结点p[find(a)]find(b);4.查询两个元素是否在一个集合我们有了find函数就可以很简单的判断出两个元素的是否在同一个集合当中两个元素是否在同一个树中。我们只需要判断两个元素集合的编号是否相同两个元素的祖宗节点是否相同即可。我们看代码12345//看a、b两个元素是否在同一个集合当中if(find(a)find(b))coutYesendl;elsecoutNoendl;5.并查集例题训练1一共有 n 个数编号是1∼n最开始每个数各自在一个集合中。现在要进行m个操作操作共有两种M a b将编号为a和b的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作Q a b询问编号为a和b的两个数是否在同一个集合中输入格式第一行输入整数n和m。接下来m行每行包含一个操作指令指令为M a b或Q a b中的一种。输出格式对于每个询问指令Q a b都要输出一个结果如果a和b在同一集合内则输出Yes否则输出No。每个结果占一行。数据范围1≤n,m≤10e5 1≤n,m≤10e5输入样例4 5M 1 2M 3 4Q 1 2Q 1 3Q 3 4输出样例YesNoYes答案如下123456789101112131415161718192021222324252627282930313233343536373839#includeiostreamusingnamespacestd;constintN100010;intp[N];//找祖宗路径压缩intfind(intx){if(p[x]!x){p[x]find(p[x]);}returnp[x];}intmain(){intn,m;scanf(%d%d,n,m);for(inti1;in;i)p[i]i;while(m--){charop[2];inta,b;cinopab;if(op[0]M){//合并 把a的祖宗节点的父节点当作b的祖宗结点p[find(a)]find(b);}else{if(find(a)find(b))coutYesendl;elsecoutNoendl;}}return0;}6.并查集例题训练2给定一个包含nn个点编号为1∼n1∼n的无向图初始时图中没有边。现在要进行mm个操作操作共有三种C a b在点aa和点bb之间连一条边aa和bb可能相等Q1 a b询问点aa和点bb是否在同一个连通块中aa和bb可能相等Q2 a询问点aa所在连通块中点的数量输入格式第一行输入整数nn和mm。接下来mm行每行包含一个操作指令指令为C a bQ1 a b或Q2 a中的一种。输出格式对于每个询问指令Q1 a b如果aa和bb在同一个连通块中则输出Yes否则输出No。对于每个询问指令Q2 a输出一个整数表示点aa所在连通块中点的数量每个结果占一行。数据范围1≤n,m≤1051≤n,m≤105输入样例5 5C 1 2Q1 1 2Q2 1C 2 5Q2 5输出样例Yes23我们这个题相对于上个题就是对出了一个统计一个集合元素的个数。整体思路大同小异我们直接看代码解析1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#includeiostreamusingnamespacestd;constintN100010;intp[N],cnt[N];intfind(intx){if(p[x]!x){p[x]find(p[x]);}returnp[x];}intmain(){intn,m;cinnm;for(inti0;in;i){p[i]i;cnt[i]1;}while(m--){charop[5];inta,b;scanf(%s,op);if(op[0]C){scanf(%d%d,a,b);if(find(a)find(b))continue;cnt[find(b)]cnt[find(a)];p[find(a)]find(b);}elseif(op[1]1){scanf(%d%d,a,b);if(find(a)find(b))printf(Yes\n);elseprintf(No\n);}else{scanf(%d,a);printf(%d\n,cnt[find(a)]);}}return0;}注意我们刚开始每个集合中的元素只有一个。后续合并后集合元素个数不断增加。三、总结我们主要掌握find函数并查集算法中最为核心的就是find函数。在这个算法中路径压缩给我们的算法效率提高了很多这个也是需要理解的。合并、查询是并查集的两个主要操作我们也应该熟悉理解。