poj2492并查集
并查集,思路:将和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
补充:web前端 , HTML 5 ,