这道题就是并查集的模板题

那么这要我们把并查集写出来，这道题基本就解决了

并查集的参考代码：

class union_find_set{
private:
	vector<int> fa;
	vector<int> dep;//秩（深度）
	int cnt;
public:
	union_find_set(int n):cnt(n){
		fa=vector<int>(n+1);
		dep=vector<int>(n+1,1);
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
        //初始化
	}
	int find(int x){
		int r=x;
		while(r!=fa[r]){
			r=fa[r];
            //找祖先
		}
		while(x!=r){
			int nxt=fa[x];
			fa[x]=r;
			x=nxt;
            //路径压缩（优化）
		}
		return r;
	}
	void union_set(int x,int y){
		int rx=find(x),ry=find(y);
		if(rx==ry){
			return;//如果在同一集合，那么不用合并
		}
		if(dep[rx]<dep[ry]){
			swap(rx,ry);
		}
		fa[ry]=rx;
		if(dep[rx]==dep[ry]){
			dep[rx]++;
		}
        //按秩合并
		cnt--;//集合数-1
	}
	int count(){
		return cnt;
	}
};

关键部分：

scanf("%d%d%d",&op,&u,&v);
if(op==1){
	bool is=(s.find(u)==s.find(v));//如果在同一集合（连通），那么结果为1，否者为0
	ans=(ans*2+is)%mod;//计算
}else{
	s.union_set(u,v);//加入这条边（让节点u,v连通）
}

最后粘上完整代码：

#include<bits/stdc++.h>

using namespace std;
class union_find_set{
private:
	vector<int> fa;
	vector<int> dep;
	int cnt;
public:
	union_find_set(int n):cnt(n){
		fa=vector<int>(n+1);
		dep=vector<int>(n+1,1);
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
	}
	int find(int x){
		int r=x;
		while(r!=fa[r]){
			r=fa[r];
		}
		while(x!=r){
			int nxt=fa[x];
			fa[x]=r;
			x=nxt;
		}
		return r;
	}
	void union_set(int x,int y){
		int rx=find(x),ry=find(y);
		if(rx==ry){
			return;
		}
		if(dep[rx]<dep[ry]){
			swap(rx,ry);
		}
		fa[ry]=rx;
		if(dep[rx]==dep[ry]){
			dep[rx]++;
		}
		cnt--;
	}
	int count(){
		return cnt;
	}
};
int n,m,op,u,v;
int ans=0;
int mod=998244353;
int main(){
	scanf("%d%d",&n,&m);
	union_find_set s(n);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&op,&u,&v);
		if(op==1){
			bool is=(s.find(u)==s.find(v));
			ans=(ans*2+is)%mod;
		}else{
			s.union_set(u,v);
		}
	}
	printf("%d",ans);
	return 0;
}

完结撒花！