Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:ac代码！

Posted by 2341305086 at 2024-04-08 19:40:46 on Problem 1182
In Reply To:ac代码！ Posted by:mc77xy at 2020-02-03 14:27:59
> #include<cstdio>
> #include<cstring>
> #include<iostream>
> #include<algorithm>
> using namespace std;
> #define N 50000
> int fa[N],ran[N],n;
> inline void init(){
> 	for(int i=1;i<=n;i++){
> 		fa[i]=i;
> 		ran[i]=0;
> 	}
> }
> int find(int x){
> 	if(x==fa[x])
> 		return x;
> 	int t=fa[x];
> 	fa[x]=find(fa[x]);
> 	ran[x]=(ran[x]+ran[t])%3;
> 	return fa[x];
> }
> inline void merge(int i,int j,int d){
> 	int x=find(i),y=find(j);
> 	if(x==y)	return;
> 	fa[y]=x;
> 	ran[y]=(3-ran[j]+d-1+ran[i])%3;
> }
> int main(){
> 	int m,a,b,d,i,ans=0;
> 	scanf("%d%d",&n,&m);
> 	init();
> 	while(m--){
> 		scanf("%d%d%d",&d,&a,&b);
> 		if(a>n||b>n||(d==2&&a==b))	ans++;
> 		else if(find(a)==find(b)){
> 			if(d==1&&ran[a]!=ran[b])	ans++;
> 			if(d==2&&(ran[a]+1)%3!=ran[b])	ans++;
> 		}
> 		else
> 			merge(a,b,d);
> 	}
> 	printf("%d\n",ans);
> }

Followed by: