首先我们知道并查集是为了解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中。
下面是一道模板题。
题目如下：
维护一个 n 点的无向图，支持：
- 加入一条连接 u 和 v 的无向边
- 查询 u和 v的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用 0 或 1代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 的值。
请务必使用快读。
输入格式
第一行包含两个整数 n,m表示点的个数和操作的数目。
接下来 m 行每行包括三个整数 op,u,v。
- 如果 op=0，则表示加入一条连接 u 和 v 的无向边；
- 如果 op=1，则表示查询 u 和 v 的连通性。
输出格式
一行包括一个整数表示答案。
样例
| Input | Output |
1. 3 6 2. 1 1 0 3. 0 0 1 4. 1 0 1 5. 1 1 2 6. 0 2 1 7. 1 2 1 |
5
|
答案串为 0101。
数据范围与提示
n≤4000000,m≤8000000
下面我们分析一下这个题目；
拿样例解释一下；比如开头1 1 0；就代表查询1 0，是否连接，不连接就输出0，而后面的 0 0 1，表示连接 0 1，所以后面的1 0 1，在查询后显示0 1连接即输出1，依此类推，得到答案串0101；
下面是ac代码，关建点都有注释。
学习算法
#include<iostream> using namespace std; int father[4000000]; long long ans=0; int k=1; int temp; const long long mod=998244353; int find(int k)//父亲节点 { if(father[k]!=k)//这里的意思是如果一个节点不等于他自己就不是根节点，然后递归 return find(father[k]); return father[k]; } void unionn(int x,int y)//连接 { x=find(x); y=find(y); if(x!=y) father[y]=x; } int main() { int m,n,i,a,b,s1,s2,op; cin>>n>>m; for(i=1;i<=n;i++)//先自己就是自己的父亲节点 father[i]=i; for(i=1;i<=m;i++) { scanf("%d %d %d",&op,&a,&b); if(op==0) { unionn(a,b);//连接边 } else { if(find(a)==find(b))//如果父亲节点相同 { ans*=2; ans++; ans%=mod; } else { ans*=2; ans%=mod; } } } cout<<ans<<endl;//ok }
学习算法
