脚本宝典收集整理的这篇文章主要介绍了html5教程-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
并查集,思路:将和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
觉得可用,就经常来吧! 脚本宝典 欢迎评论哦! html5教程,巧夺天工,精雕玉琢。小宝典献丑了!
以上是脚本宝典为你收集整理的html5教程-poj2492并查集全部内容,希望文章能够帮你解决html5教程-poj2492并查集所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。