P2024 食物链
这道题我用了两种方法，也是刚学（发现并查集学的太少了）
一个是种类并查集，另一个是带权并查集
1种类并查集
题目中有三种关系，分别是吃，被吃和同类；还有三类集合（三种动物），所以就构建出三个集合，且使各个集合之间分别表示这三种关系；
构建三个集合A,B,C;其中A吃B,B吃C，C吃A
对于输入的一对关系，如果是x吃y，则构建吃的关系，即将A中的x和B中的y放入一个集合，B中x和C中y放入一个集合，C中的x和A中的y放入一个集合（因为不知道x和y分别具体属于哪一类，所以都要处理）
而如果是x与y同类，则将A中x，A中y放入同一集合，同理B,C中x和y做同样处理
咳咳，这都是真话才做上边的操作，那怎么判断是不是真话呢？如果输入x吃y，那你就看B中的x和A中的y是不是同一集合（不用看C和B，A和C了，因为修改集合的时候都是一样改的），如果是，那就是之前说过y吃x了，那这句就是假话，你再看A中（不用看B,C了，因为一样）是不是x和y在同一集合，如果是，那就是之前说过x和y是同类，那也说明这句是假话；
ok，下边是代码（我用的是1-n表示A，n+1-2n表示B，2n+1-3*n表示C)
（其实谁吃谁，谁是谁的父亲怎么设没关系）
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,cnt;
int fa[200050];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main()
{
// freopen("P2024_2.in","r",stdin);
// freopen("666.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=3*n;i++)fa[i]=i;
for(int i=1;i<=k;i++)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(x>n||y>n||(x==y&&op==2))
{
cnt++;
continue;
}
if(op==1)
{
if(find(x)==find(y+n)||find(y)==find(x+n))
{
cnt++;
continue;
}
fa[find(x)]=find(y);
fa[find(x+n)]=find(y+n);
fa[find(x+2*n)]=find(y+2*n);
}else
{
if(find(x)==find(y)||find(x+n)==find(y))
{
cnt++;
continue;
}
fa[find(x)]=find(y+n);
fa[find(x+n)]=find(y+2*n);
fa[find(x+2*n)]=find(y);
}
}
cout<<cnt<<endl;
return 0;
}
2带权并查集
带权并查集其实就是在一个点和父亲的边上加了个权值
不好理解的地方就是合并的时候
我用fa[x]=y,v[x]=0表示是同类；fa[x]=y,v[x]=1表示x吃y；fa[x]=y,v[x]=2表示x被y吃；
(下面用箭头表示指向父亲)
可以手推一下，如果x->y->z->k->t（都是吃的关系）
那v[x]=v[y]=v[z]=v[k]=1,v[t]=0(初值为零);
路径压缩之后就是v[t]=0,v[k]=1,v[z]=2,v[y]=0,v[x]=1;
可以发现就是mod3的过程；
也就是v[x]=(v[x]+v[fa[x]])%3且必须先更新fa[x]，所以路径压缩的时候递归改权值即可，如下
int find(int x)
{
int t=fa[x];
if(fa[x]!=x)fa[x]=find(fa[x]);
val[x]=(val[t]+val[x]+3)%3;
return fa[x];
}
那合并呢？（用Px表示x的根节点）
由于x和Py只有一种关系，儿有两条路径可以找到这关系
一条是x->Px->Py;
另一条是x->y->Py;
推式子让这两条路径求的关系相同
即v[x]+v[Px]=(x和y的关系)+v[y]（这里v[x]和v[y]都是到根节点的v值（即路径压缩之后的）），移项就可以求出v[Px]，我们要做的是在合并之前将v[Px]给它赋上值，然后合并就好了（有个注意事项，就是你赋值之后下面的合并你就不能再调用find函数了，因为这个时候你调用，那Px的v值已经改了，但它父亲还没改成Py，这就不对了，所以必须提前定义（不信你可以试试，我下面标注了））
还有，为了防止出现移项出现减法之后出现负数的情况，最好是加三再取模
下面是代码
正确的
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10;
int n,k;
int fa[N],val[N],cnt;
int find(int x)
{
int t=fa[x];
if(fa[x]!=x)fa[x]=find(fa[x]);
val[x]=(val[t]+val[x]+3)%3;
return fa[x];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)fa[i]=i,val[i]=0;
for(int i=1;i<=k;i++)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if((x==y&&op==2)||x>n||y>n)
{
cnt++;
continue;
}
int fx=find(x);//就是这里，你再看看下面的错误的
int fy=find(y);
if(op==1)
{
if(fx!=fy)
{
val[fx]=(-val[x]+val[y]+3)%3;
fa[fx]=fy;
}else if((val[x]-val[y]+3)%3!=0)cnt++;
}else
{
if(fx!=fy)
{
val[fx]=((-val[x]+val[y]+1)%3+3)%3;
fa[fx]=fy;
}else if(((val[x]-val[y])%3+3)%3!=1)cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
错误的
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10;
int n,k;
int fa[N],val[N],cnt;
int find(int x)
{
int t=fa[x];
if(fa[x]!=x)fa[x]=find(fa[x]);
val[x]=(val[t]+val[x]+3)%3;
return fa[x];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)fa[i]=i,val[i]=0;
for(int i=1;i<=k;i++)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if((x==y&&op==2)||x>n||y>n)
{
cnt++;
continue;
}
if(op==1)
{
if(find(x)!=find(y))
{
val[find(x)]=(-val[x]+val[y]+3)%3;
fa[find(x)]=find(y);
}else if((val[x]-val[y]+3)%3!=0)cnt++,cout<<i<<endl;
}else
{
if(find(x)!=find(y))
{
val[find(x)]=((-val[x]+val[y]+1)%3+3)%3;
fa[find(x)]=find(y);
}else if(((val[x]-val[y])%3+3)%3!=1)cnt++,cout<<i<<endl;
}
}
cout<<cnt<<endl;
return 0;
}