突然发现自己不知道这是什么东西。。。

感觉好像就是在并查集的基础上多维护了一些有用的量

然后做了一道大水题

poj 1182 食物链

题解可见 写的挺清楚

我就插个代码在这

1 //poj 1182 2  3 ll read() 4 { 5     ll x=0,f=1; 6     char ch=getchar(); 7     while(ch<'0'||ch>'9') 8     { 9         if(ch=='-')f=-1;10         ch=getchar();11     }12     while(ch>='0'&&ch<='9')13     {14         x=x*10+ch-'0';15         ch=getchar();16     }17     return x*f;18 }19 20 void print(ll x)21 {22     if(x<0)putchar('-'),x=-x;23     short a[20]= {},sz=0;24     while(x>0)a[sz++]=x%10,x/=10;25     if(sz==0)putchar('0');26     for(ll i=sz-1; i>=0; i--)putchar('0'+a[i]);27 }28 29 const ll mod=1e9+7;30 31 int n,k;32 int fa[111111];33 int sy[111111];34 35 int fnd(int x){36     if(fa[x]==x) return x;37     else{38         int nw=fa[x];39         fa[x]=fnd(fa[x]);40         sy[x]=(sy[nw]+sy[x])%3;41         return fa[x];42     }43 }44 45 bool check(int tp,int x,int y){46     if(x>n || y>n) return 0;47     if(tp==1 && x==y) return 0;48     int fx=fnd(x),fy=fnd(y);49     if(fx==fy)50         if((sy[x]-sy[y]+3)%3==tp) return 1;51         else return 0;52         53     return 1;54 }55 56 void uni(int tp,int x,int y){57     int fx=fnd(x),fy=fnd(y);58     if(fx!=fy){59         fa[fx]=fy;60         sy[fx]=(sy[y]-sy[x]+tp+3)%3;61     }62 }63 64 int main(){65     #ifdef LZT66         freopen("in","r",stdin);67     #endif68     n=read();k=read();69     70     for(int i=1;i<=n;i++)71         fa[i]=i;72     73     int ans=0;74     while(k--){75         int tp=read(),x=read(),y=read();76         tp--;77         if(check(tp,x,y))78             uni(tp,x,y);79         else80             ans++;81     }82     83     print(ans);84     puts("");85     return 0;86 }