学步园

  并查集，思路：将和bug i interact（我觉得“性交”会有误会）的归为一类，看同类的是否有interact行为（性行为），如果有输出Suspicious bugs found!

#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++;
	}
}