这题就一组数据,用while(scnaf(“%d%d”,&n,&m)!=EOF)..就wa了,我wa了数次,无语了。。
带权值的并查集,
d[]数组存的是每个点和根节点的关系,同类为d[i]=0; 根节点 吃 i点为d[i]=1; i点吃根节点为d[i]=2;
自己画图感受一下吧!!
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int f[50050],d[50050];
int root(int p)
{
if(f[p]==-1) return p;
else {
int fa=f[p];
f[p]=root(f[p]);//递归先找d[fa],下一步d[p]=(d[p]+d[fa])%3;才能执行
d[p]=(d[p]+d[fa])%3;
return f[p];
}
}
void merge(int a,int b,int c)
{
int aa=root(a);
int bb=root(b);
f[bb]=aa;
d[bb]=(d[a]-d[b]+c+3)%3;
}
int main()
{
int i,j,k;
int n,m;
scanf("%d%d",&n,&m);
int a,b,c,sum=0;
memset(d,0,sizeof(d));
memset(f,-1,sizeof(f));
while(m--){
scanf("%d%d%d",&a,&b,&c);
if(b>n || c>n) sum++;
else{
if(a==1){
if(root(b)!=root(c))
merge(b,c,0);
else if(d[c]!=d[b]) sum++;
}
else{
if(root(b)!=root(c))
merge(b,c,1);
else if(((d[c]-d[b]-1)%3)!=0) sum++;
}
}
}
printf("%d\n",sum);
}