讨论 / C++ AC
1729709860 2017-04-28 22:28:59
点我顶贴 收藏 删除
#include<iostream>

#include<cstring>

using namespace std;

#define maxn 50005

int p[maxn<<2];//p[x]表示x的同类,p[x+n]表示x吃的,p[x+2n]表示吃x的//

int n;

int find(int x) //查询+压缩路径

{

int s=x;

while(p[s]>0) s=p[s];

int tem;

while(p[x]>0)

{

tem=p[x];

p[x]=s;

x=tem;

}

return s;

}

void un(int x,int y) //连接

{

int a=find(x),b=find(y);

if(a==b) return;

if(p[a]<p[b])

{

p[a]+=p[b];

p[b]=a;

}

else

{

p[b]+=p[a];

p[a]=b;

}

}

int pt(int x,int y) //判断同类

{

if(x>n||y>n||x<=0||y<=0) return 0;

if(find(x+n)==find(y)||find(x+2*n)==find(y)) return 0;

return 1;

}

int pc(int x,int y) //判断吃

{

if(x>n||y>n||x<=0||y<=0) return 0;

if(find(x)==find(y)||find(x+2*n)==find(y)) return 0;

return 1;

}

int main()

{

int k,x,y;

memset(p,-1,sizeof(p));

int ans=0;

cin>>n>>k;

int a;

for(int i=1;i<=k;i++)

{

cin>>a>>x>>y;

if(a==1)

{

if(pt(x,y))

{

un(x,y);

un(x+n,y+n);

un(x+2*n,y+2*n);

}

else

ans++;

}

else

{

if(pc(x,y))

{

un(x+n,y);

un(x,y+2*n);

un(x+2*n,y+n);

}

else

ans++;

}

}

cout<<ans<<endl;

}

查看更多回复
提交回复