当前位置:编程学习 > html/css >>

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 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,