我用的是带权并查集。 rel[rel[x ]]存的是x和 fa[fa[x ]]的关系,但是wa了第三个点。求大佬帮忙调调。
捞一个月了,发酵了
#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void R(T& t){
t=0; register char ch=getchar();
while(!('0'<=ch&&ch<='9')){ if(ch=='-') t*=-1; ch=getchar(); }
while(('0'<=ch&&ch<='9')){ t=((t<<1)+(t<<3))+ch-'0'; ch=getchar(); }
}
template <typename T,typename... Args> inline void R(T& t, Args&... args){R(t);R(args...);}
template <typename T>inline void W(T x){
if(x<0) putchar('-'),x=~(x-1); int s[30],top=0; while(x) s[++top]=x%10,x/=10;
if(!top) s[++top]=0; while(top) putchar(s[top--]+'0');
}
//0 表示同类 1 表示吃 2表示被吃
int fa[100086];
int rel[100086];
int n,m,ans;
int findf(int x){
if(fa[x]==x) return x;
int root=findf(fa[x]);
//因为要路径压缩,那么他直接到根的关系应该是他跟他爸爸的关系再加上他爸爸跟他爷爷的关系
rel[x]=(rel[fa[x]]+rel[x]+3)%3;
fa[x]=root;
return root;
}
int unity(int x,int y,int c){
int a=findf(x),b=findf(y);
if(c==1) c--;
if(a==b){
if(c==0){
if(rel[x]==rel[y]) return 1;
else return 0;
}else{
//x吃y
//如果x和root是同类,那么如果x吃y的话,
if(rel[x]==0&&rel[y]!=2) return 0;
//如果x吃root,那么如果x吃y的话
if(rel[x]==1&&rel[y]!=0) return 0;
//如果x被root吃,那么如果x吃y的话
if(rel[x]==2&&rel[y]!=1) return 0;
return 1;
}
}else{
//b子树挂到a上
fa[b]=a;
//处理b和a的关系
rel[b]=(rel[x]+c-rel[y]+3)%3;
findf(x);findf(y);//路径压缩一下
return 1;
}
}
int main(){
R(n,m);
for(int i=1;i<=n;++i) fa[i]=i,rel[i]=0;
for(int i=1;i<=m;++i){
int a,b,c;
R(a,b,c);
if(b==c&&a==1) continue;
if(b==c&&a==2){
ans++;
continue;
}
if(c>n||b>n){
ans++;
continue;
}else if(unity(b,c,a)==0) ans++;
}
cout<<ans<<endl;
return 0;
}