30pts(求调或证伪)
查看原帖
30pts(求调或证伪)
1030785
wangtingmu楼主2024/8/9 15:38
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5; 
int n,m;
set<int > S[maxn];
int fa[maxn];
int find_(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find_(fa[x]);
}
void union_(int x,int y){
	int k1=find_(x);
	int k2=find_(y);
	fa[k1]=k2;
}
int ans=0,cnt=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int flag;
		scanf("%d",&flag);
		if(flag==1){
			int x,y;
			scanf("%d%d",&x,&y);
			if(x>n||y>n){
				ans++;
				continue;
			}
			int k1=find_(x);
			int k2=find_(y);
			if(S[k1].count(k2)||S[k2].count(k1)) ans++; 
			else {union_(k1,k2);}
		}
		else{
			int x,y;
			scanf("%d%d",&x,&y);
			if(x==y||find_(x)==find_(y)||x>n||y>n){
				ans++;
				continue;
			}
			int k1=find_(x),k2=find_(y);
			S[k1].insert(k2);
		}
	}
	printf("%d\n",ans);
	return 0;
}
2024/8/9 15:38
加载中...