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