POJ 1182 食物链 并查集

带权并查集

#include <cstdio>
using namespace std;
int f[50005],q,w,e,d[50005],ans=0,n,k;
int find(int x)
{
    if(x==f[x]) return x;
    int fx=find(f[x]);
    d[x]=(d[x]+d[f[x]])%3;
    return f[x]=fx;
}
void join()
{
    int fx=find(w),fy=find(e);
    if(fx==fy)
    {
        if(q==1&&d[w]!=d[e]) ans++;
        if(q==2&&(d[w]-d[e]+3)%3!=1) ans++;
    }
    else
    {
        if(q==1)
        {
            f[fx]=fy;
            d[fx]=(d[e]-d[w]+3)%3;
        }
        else
        {
            f[fx]=fy;
            d[fx]=(d[e]-d[w]+3+1)%3;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int ii=1;ii<=k;ii++)
    {
        scanf("%d%d%d",&q,&w,&e);
        if(w==e&&q==2||w>n||e>n){ans++;continue;}
        join();
    }
    printf("%d",ans);
}

后来 又写了一遍。。

//By SiriusRen
#include <cstdio>
using namespace std;
int f[50050],d[50050],n,k,xx,yy,zz,ans=0;
int find(int x){
    if(x==f[x])return x;
    int y=f[x];
    f[x]=find(f[x]);
    d[x]=(d[x]+d[y])%3;
    return f[x];
}
void join(int x,int y,int w){
    int fx=find(x),fy=find(y);
    if(fx!=fy) f[fx]=fy,d[fx]=(d[y]-d[x]+w+3)%3;
    else{
        if(!zz&&d[x]!=d[y])ans++;
        else if(zz&&(d[x]-d[y]+3)%3!=1)ans++;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&zz,&xx,&yy);zz--;
        if(xx>n||yy>n||(xx==yy&&zz)){ans++;continue;}
        join(xx,yy,zz);
    }
    printf("%d
",ans);
}