2 3 3 1 2 2 3 1 3 4 2 1 2 3 4
Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found!HintHuge input,scanf is recommended.
貌似这个问题属于带权并查集
但是我就生生的使用了集合的关系
首先所有昆虫应该属于两个集合
但是仅从每组输入,我们并不知道昆虫属于哪个集合
因此只能给他们各自一个集合
如果A B然后又有A C我们可以判断B与C属于一个集合
如果我们发现两个属于同一个集合,或者两个的对立集合是同一个集合
则两者同性,发生bug
不发生bug的两个发生关系,那么应该合并a和b的对立集合,b和a的对立集合
具体代码见下
#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;
const int M=2005;
map<int,int> uf; //昆虫所在集合
map<int,int> op; //昆虫对立性别所在集合
int find(int i)
{
if(i==uf[i])
return i;
return uf[i]=find(uf[i]);
}
void merge(int i,int j)
{
int t1=find(i);
int t2=find(j);
if(t1==t2)
return;
uf[t2]=t1;
merge(op[t2],op[t1]); //同时要合并对立集合
}
int main()
{
//freopen("1.in","r",stdin);
int n,m;
int t;
int co=1;
int i1,i2;
int f;
scanf("%d",&t);
while(t--)
{
f=0;
uf.clear();
op.clear();
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&i1,&i2);
if(f)
continue;
if(!uf[i1])
uf[i1]=i1;
if(!uf[i2])
uf[i2]=i2;
if(find(i1)==find(i2))
f=1;
else
{
int par1=find(i1);
int par2=find(i2);
if(!op[par1])
op[par1]=par2;
if(!op[par2])
op[par2]=par1;
if(find(op[par1])==find(op[par2]))
f=1;
else
{
merge(op[par1],i2);
merge(op[par2],i1);
}
}
}
printf("Scenario #%d:\n",co++);
if(f)
printf("Suspicious bugs found!\n\n");
else
printf("No suspicious bugs found!\n\n");
}
return 0;
}