定义

并查集是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题

构成

一般由一个数组pre[ ]，和两个函数find（），join（）构成

说明

pre[ ] :用于存储其父节点；例如pre[3]=5,即3的父节点为5

find( ): 用于寻找根节点

join（）：用于合并

PS.总之并查集就是将有关联数据分成几个集合，集合内部又有各自附属关系，然后寻找，判断，元素之间的相关性，如：1>>5>>6>>2>>4 ：2是4的父节点，6是2的父节点。。。以此类推，在这个例子中，1为根节点，也是这个“集合”的“标识”，即，我们在查询时，通常来寻找根节点来判断元素直接是否有关联，这里就是用了find（）函数

函数

find：

int find(int s)
{
	return pre[s] = (pre[s]==s?s:b[find(pre[s])]);
}

这是一个采用了路径压缩优化的find函数，用来寻找根节点，也可以用while暴力遍历但不推荐

join：

void join(int x,int y)
{
	int rootx=find(x);
	int rooty=find(y);
	if(rootx!=rooty)
		b[x]=rooty;
}

不难理解，直接把x接到y的根上

实战

题目：

维护一个 n 点的无向图，支持：

加入一条连接 u 和 v 的无向边
查询 u 和 v 的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用 0 或 1 代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 的值。

请务必使用快读。

输入格式

第一行包含两个整数 n,m，表示点的个数和操作的数目。

接下来 m 行每行包括三个整数 op,u,v。

如果 op=0，则表示加入一条连接 u 和 v 的无向边；
如果 op=1，则表示查询 u 和 v 的连通性。

输出格式

一行包括一个整数表示答案。

样例输入：

3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1

样例输出：

c++实现

#include<iostream>
#include<string>
#include<vector>
using namespace std;
long long m,n,num=0,sum=0;
vector<long long>  b;
vector<char> c;
long long ans=0,moe=998244353;
struct date
{
    int op;
    int u;
    int v;
}; //a[10086];
vector<date> a(100);
int find(int s)
{
	return b[s] = (b[s]==s?s:b[find(b[s])]);
}
void bing(int x,int y)
{
	int rootx=find(x);
	int rooty=find(y);
	if(rootx!=rooty)
	{
		b[x]=rooty;
	}
}
int main()
{  
   
    cin>>n>>m;
    b.resize(n);
    for(int i=0;i<n;i++)
        b[i]=i;
    a.resize(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].op>>a[i].u>>a[i].v;
        if(a[i].op==0) 
        {
            bing(a[i].u,a[i].v);
        } 
		else
		{
		    ans<<=1;
		    ans|=(find(a[i].u)==find(a[i].v));
		    ans%=moe;
		}
    }
    cout<<ans;
	return 0;
}

说明：这里的b数组就是pre数组，bing函数就是join

<<是左移运算符(二进制)，左移后右边位置用0补齐,比如0001>>2后为0100

|是按位或运算符：对于两个操作数的每一位，如果至少有一位是1，那结果的对应位就是1；否则是零。

定义

构成

说明

函数

实战

题目：

c++实现

c++杂记 —字符串和有趣的函数

归并排序