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 ,