lb2003的个人博客

两种做法。
扩展域不bb了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=5e4+3;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int fa[N*3];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
// 1~n,1~n same 1~n,n+1~2*n x是y的天敌 1~n,2*n+1~2*n x是y的肉食  
int main()
{
    int n,m;qr(n),qr(m);int ans=0;
    for(int i=1;i<=n*3;i++)fa[i]=i;
    for(int i=1,x,y,op;i<=m;i++)
    {
        qr(op),qr(x),qr(y);
        if(x>n||y>n||(x==y&&op==2)){++ans;continue;}
        if(op==1)
        {
            int x1=x,x2=x+n,x3=x+2*n;
            int y1=y,y2=y+n,y3=y+2*n;
            if(get(x1)==get(y2)||get(x1)==get(y3)){++ans;continue;}
            int p=get(x1),q=get(y1);fa[p]=q;
                p=get(x2),q=get(y2);fa[p]=q;
                p=get(x3),q=get(y3);fa[p]=q;
        }
        else
        {
            int x1=x,x2=x+n,x3=x+2*n;
            int y1=y+n,y2=y+2*n,y3=y;
            if(get(x1)==get(y2)||get(x1)==get(y3)){++ans;continue;}
            int p=get(x1),q=get(y1);fa[p]=q;
                p=get(x2),q=get(y2);fa[p]=q;
                p=get(x3),q=get(y3);fa[p]=q;
        }
    }
    qw(ans);puts("");
    return 0;
}

边带权
$d[x]=1 fa[x]$被吃了，$d[x]=2 x$被吃了，$d[x]=0 fa[x]$与$x$为同类。
那么关于合并的处理,$ans=d[x]+d[p]+(3-d[y])$，由于边是向上传递的，也就是$y$这条边，要逆回$y$，则权值就为$3-d[y]$
关于判断合法，x与y的关系也就是$d[x]-d[y]$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=5e4+4;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int fa[N],d[N];
// d[x]=1 fa[x]被吃了 d[x]=2 x被吃了 d[x]=0 fa[x]与x为同类 
int get(int x)
{
    if(x==fa[x])return x;
    int root=get(fa[x]);
    d[x]=(d[x]+d[fa[x]])%3;
    return fa[x]=root;
}
int main()
{
    int n,m;qr(n),qr(m);int ans=0;
    for(int i=1;i<=n;i++)fa[i]=i,d[i]=0;
    for(int i=1;i<=m;i++)
    {
        int op,x,y;qr(op),qr(x),qr(y);
        int p=get(x),q=get(y);
        if(x>n||y>n||(x==y&&op==2)){++ans;continue;}
        if(p!=q)
        {
            fa[p]=q;
            if(op==2)d[p]=(d[y]-d[x]+4)%3;
            if(op==1)d[p]=(d[y]-d[x]+3)%3;
        }
        else
        {
            if(op==2&&(d[x]-d[y]+3)%3!=1)++ans;
            if(op==1&&(d[x]-d[y]+3)%3!=0)++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}