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;

}

巴特西

UVA 10158 War（并查集）

最新文章

热门文章