首页 > 代码库 > UVA 10158 War

UVA 10158 War

//思路详见课本 P 214 页

思路:直接用并查集,set [ k ]  存 k 的朋友所在集合的代表元素,set [ k + n ] 存 k  的敌人 所在集合的代表元素。

 

#include<iostream>#include<cstring>using namespace std;const int maxn=2 *10000 +100;int set[maxn];int n;int set_find(int d){	if(set[d]<0)		return d;	return set[d]=set_find(set[d]);}int arefriends(int x,int y){	if( ( set_find(x)!=set_find(y) ) &&( set_find(x)!=set_find(y+n) ) )         // ----------   不确定关系----- 返回 -1		return -1;	else if(set_find(x)==set_find(y))         // ----------   是朋友----- 返回 1		return 1;	return 0;        //----------  是敌人----- 返回 0}int areenemies(int x,int y){	if(arefriends(x,y)==-1)         // ---------- 不确定关系----- 返回 -1		return -1;	else if(arefriends(x,y)==1)         //  ----------   是朋友-----  返回 0		return 0;	return 1;      // ----------  是敌人----- 返回 1}void setfriends(int x,int y)//----------是敌人------输出 -1{	if(arefriends(x,y)==0)		cout<<-1<<endl;	else if( arefriends(x,y)==-1 )//---当时我把括号写错了  -- -->else if( arefriends(x,y==-1) ),出现了 runtime error	{		set[set_find(x)]=set_find(y);		set[set_find(x+n)]=set_find(y+n);	}}void setenemies(int x,int y){	if(arefriends(x,y)==1)       //---------是朋友----------输出 -1		cout<<-1<<endl;	else if(arefriends(x,y)==-1)	{		set[set_find(x+n)]=set_find(y);		set[set_find(x)]=set_find(y+n);	}}int main(){	memset(set,-1,sizeof(set));	cin>>n;		int c,x,y;	while(cin>>c>>x>>y)	{		if(c==0 && x==0 &&y==0)			break;		if(c==1)			setfriends(x,y);		else if(c==2)			setenemies(x,y);		else if(c==3)			cout<< ( arefriends(x,y)==1?1:0 ) <<endl;		else if(c==4)			cout<< ( areenemies(x,y)==1?1:0 ) <<endl;	}	return 0;}