我要评论并查集，思路：将和bug i interact（我觉得“性交”会有误会）的归为一类，看同类的是否有interact行为（性行为），如果有输出suspicious bugs found!
[html]
#include <iostream>
using namespace std;
class node
{
public:
node()
{
nodeid=0;
parent=null;
rank=0;
}
node(int id)
{
nodeid=id;
parent=null;
rank=0;
}
int nodeid;
node* parent;
int rank;
};
void makeset(node* node)
{
node->parent=node;
node->rank=0;
}
void linksets(node* node1,node* node2)
{
if(node1->rank>node2->rank)
{
node2->parent=node1;
}
else if(node1->rank<node2->rank)
{
node1->parent=node2;
}
else
{
node1->parent=node2;
node2->rank++;
}
return ;
}
node* findsets(node* node)
{
if(node->parent!=node)
{
node->parent=findsets(node->parent);
}
return node->parent;
}
void unionsets(node* node1,node* node2)
{
linksets(findsets(node1),findsets(node2));
}
int main()
{
node* pnode[2002];
node* plinknode[2002];
int iscenario,icount;
cin>>iscenario;
icount=1;
while(icount<=iscenario)
{
int inumber,iinteraction;
scanf("%d%d",&inumber,&iinteraction);
for(int i=0;i<inumber;i++)
{
pnode[i]=new node(i+1);
makeset(pnode[i]);
plinknode[i]=null;
}
bool flag=true;
int ibug1,ibug2;
for(int i=0;i<iinteraction;i++)
{
scanf("%d%d",&ibug1,&ibug2);
if(findsets(pnode[ibug1-1]) != findsets(pnode[ibug2-1]) )
{
if(plinknode[ibug1-1]==null)
{
plinknode[ibug1-1]=pnode[ibug2-1];
}
else
{
unionsets(pnode[ibug2-1],plinknode[ibug1-1]);
}
if(plinknode[ibug2-1]==null)
{
plinknode[ibug2-1]=pnode[ibug1-1];
}
else
{
unionsets(plinknode[ibug2-1],pnode[ibug1-1]);
}
}
else
{
flag=false;
}
}
printf("scenario #%d:\n",icount);
if(flag==false)
{
printf("suspicious bugs found!\n\n");
}
else
{
printf("no suspicious bugs found!\n\n");
}
icount++;
}
}
作者：qiul12345
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论