首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。