种类并查集 把find变成查索引 unity变成x是y的

真假英雄 http://oj.saikr.com/contest/20/problem/K

在一个小镇上，很多人都患了一个精神病，他们都认为自己是“英雄”或者“反派”中间的一种，“英雄”觉得自己是正义的一方，所以当你问起他谁是“英雄”时，他会直接按照自己心里的话说对方的身份，“反派”觉得不能暴露自己的身份，所以对于你的问他谁的身份时，他都会说谎话，即把“英雄”说成“反派”，“反派”说成是“英雄”。现在假设有n个人，你询问了m次，而你现在需要判断的，是“英雄”最多可能有多少个·。若出现无解的情况，请输出-1.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int fa[N],sz[N],n,m,ans;
int read(){
	int x=0,w=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*w;
}

int find(int x){
	if(fa[x]==x)return fa[x];
	fa[x]=find(fa[x]);
	sz[fa[x]]+=sz[x];
	sz[x]=0;
	return fa[x];
}

void mer(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy){
		sz[fx]+=sz[fy];sz[fy]=0;
		fa[fy]=fx;
	}
}
//以上是并查集 
int main(){
	n=read();m=read();ans=0;
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)sz[i]=0;
	for(int i=1+n;i<=2*n;i++)sz[i]=1;//预处理 
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		int fx=find(x),fy=find(y),fxn=find(x+n),fyn=find(y+n);//假定x,y表示坏人，x+n,y+n表示好人 
		string ch;cin>>ch;
		if(ch=="good"){
			mer(x,y);mer(y+n,x+n);//如果x说y是好人，则x,y要么同时是好人，要么同时是坏人 
		}else {
			mer(x+n,y);mer(y+n,x);//如果x说y是坏人，则x,y一定有一好一坏的情况 
		}
	}
	for(int i=1;i<=n;i++){
		cout<<fa[i]<<" "; 
		if(find(i)==find(i+n)){cout<<-1<<endl;return 0;}//如果出现了i既是好人又是坏人的情况，则无解 
	}
	cout<<endl<<endl;
	for(int i=1;i<=n;i++) cout<<fa[i]<<" ";
	cout<<endl<<"end"<<endl;;
	for(int i=1;i<=n;i++){
		
		ans+=max(sz[find(i)],sz[find(i+n)]);//统计答案 ,取max是因为贪心取最大就好，因为两个不同条件的成立带来的影响是不一样的 
		cout<<ans<<endl;
		sz[find(i)]=sz[find(i+n)]=0;//注意清0，因为之前已经统计过答案了 
	}cout<<ans<<endl;	
	return 0;
}

食物链

一倍存本身，二倍存猎物，三倍存天敌
唯一容易忽略的点就是：一的猎物的猎物 就是一的天敌

#include<cstdio>
int fa[300005];
int n,k,ans;
inline int read()
{
    int sum=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
    return sum;
}//读入优化
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}//查询
int unity(int x,int y)
{
    int r1=find(fa[x]),r2=find(fa[y]);
    fa[r1]=r2;
}//合并
int main()
{
    int x,y,z;
    n=read(),k=read();
    for(int i=1;i<=3*n;++i) fa[i]=i; //对于每种生物：设 x 为本身，x+n 为猎物，x+2*n 为天敌
    for(int i=1;i<=k;++i) 
    {
        z=read(),x=read(),y=read();
        if(x>n||y>n) {ans++; continue;} // 不属于该食物链显然为假
        if(z==1)
        {
            if(find(x+n)==find(y)||find(x+2*n)==find(y)) {ans++; continue;}
            //如果1是2的天敌或猎物，显然为谎言
            unity(x,y); unity(x+n,y+n); unity(x+2*n,y+2*n);
            //如果为真，那么1的同类和2的同类，1的猎物是2的猎物，1的天敌是2的天敌
        }
        else if(z==2)
        {
            if(x==y) {ans++; continue;} //其实是废话但是可以稍微省点时间
            if(find(x)==find(y)||find(x+2*n)==find(y)) {ans++; continue;}
            //如果1是2的同类或猎物，显然为谎言
            unity(x,y+2*n); unity(x+n,y); unity(x+2*n,y+n);
            //如果为真，那么1的同类是2的天敌，1的猎物是2的同类，1的天敌是2的猎物
        }
    }
    printf("%d\n",ans);
    return 0;
}