并查集是一个集合操作，将一个集合与另一个集合合并或者查询两个元素是否属于同一个集合。具体操作是先创建一个数组存放各个元素的父亲，初始给每个元素指定父亲是它自己。在合并操作时，先看看两个元素的父亲是否相同，如果相同就不变，否则就让一个的父亲等于另一个的父亲。在查询操作时，就查询两个元素的父亲是否相同，如果相同的话就是同在一个集合里面，否则就不是。并查集的核心是find函数，这个函数一般包括路径压缩的功能，即这个集合的无论多少级子元素都指向最高级的父级，也就是递归到父级等于自身时停止递归。
#include
#include
using namespace std;
const int N = 1e5 + 10;
int p[N],n,m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1;i
Original: https://www.cnblogs.com/amour233/p/16477678.html
Author: LYL233
Title: 并查集
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643981/
转载文章受原作者版权保护。转载请注明原作者出处！