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-> ranknode2-> 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; iiNumber; i++) 
        {  
            pNode[i]=new Node(i+1);  
            MakeSet(pNode[i]);  
            pLinkNode[i]=NULL;  
        }  
        bool flag=true;  
        int iBug1,iBug2;  
        for(int i=0; iiInteraction; 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-> ranknode2-> 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; iiNumber; i++) 
        {  
            pNode[i]=new Node(i+1);  
            MakeSet(pNode[i]);  
            pLinkNode[i]=NULL;  
        }  
        bool flag=true;  
        int iBug1,iBug2;  
        for(int i=0; iiInteraction; 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教程，巧夺天工，精雕玉琢。小宝典献丑了！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！