本文共 933 字，大约阅读时间需要 3 分钟。

【模板】并查集

输入格式

接下来M 行，每行包含三个整数Zi,Xi,Yi。

当Zi=1 时，将Xi与Yi所在的集合合并。

当Zi=2 时，输出Xi与Yi是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

输入输出样例

对于 70% 的数据，N≤100，M≤10³。

对于100% 的数据，1≤N≤10⁴，1≤M≤2×10⁴。

做了这么多到并查集的题目了

这道题，就是一个并查集模板（大家要学好并查集，以后有大作用哦）

#include
   
    #include
    
     using namespace std;int n,m,z,x,y,pre[10005];int find(int x)//找爸爸+路径压缩{   	if(pre[x]==0)return x;	return pre[x]=find(pre[x]);}void bcj(int x,int y)//并查集{   	int x1=find(x),y1=find(y);//找爸爸	if(x1!=y1)pre[y1]=x1;//合并}int main(){   	cin>>n>>m;	for(int i=1;i<=m;i++)	{   		cin>>z>>x>>y;		if(z==1)bcj(x,y);//如果z==1就合并集合，否则就判断集合是否一样		else if(find(x)==find(y))cout<<"Y"<
    
   

谢谢观看