#include"iostream"
using namespace std;
int num_bug;
int num_message;
int father[2005];
int opp[2005];
int rank[2005];
void make_set()
{
	for(int i=1;i<=num_bug;i++)
	{
		father[i]=i;        // 初始化每个元素的祖先是他本身。
		rank[i]=0;          // 每个元素的高度为0；
		opp[i]=-1;         // 初始化，-1表示每个元素的对立面都未出现
	}
}
int find_set(int x)
{
	if(father[x]!=x)
	{
		father[x]=find_set(father[x]);
	}
	return father[x];
}

void union_set(int x,int y)
{
	x=find_set(x);
	y=find_set(y);
	if(rank[x]>rank[y])
	{
		father[y]=x;
	}
	else if(rank[x]<rank[y])
	{
		father[x]=y;
	}
	else
	{
		father[y]=x;
		rank[x]++;
	}
}



int main()
{
	int T;
	int count=0;
    int x,y;
	cin>>T;
	while(T--)
	{
		count++;
		int flag=1;
		
		
		cin>>num_bug>>num_message;
        make_set();
		for(int i=1;i<=num_message;i++)
		{
			
			cin>>x>>y;
			if(find_set(x)==find_set(y))
				flag=0;
			else
			{
				if(opp[x]!=-1)          // 等于opp[x]!=-1时表示于x对立的点已经有出现
				{	                    // 此时要将x的对立面opp[x]和y合并。
			
					union_set(opp[x],y);
				}
				if(opp[y]!=-1)         // opp[y]!=-1,表示于y对立的一面已经出现
				{
					union_set(x,opp[y]); // 此时此时要将y的对立面opp[y]和x合并。
				}
				opp[x]=y;
				opp[y]=x;
			}
		}
		if(flag==0)
		{
			cout<<"Scenario #"<<count<<":"<<endl;
			cout<<"Suspicious bugs found!"<<endl;
			cout<<endl;
		}
		else
		{
			cout<<"Scenario #"<<count<<":"<<endl;
			cout<<"No suspicious bugs found!"<<endl;
			cout<<endl;
		}
	}
	return 1;
}

• Re:经典并查集！ 附代码！只不过时间多了些，但不知为什么能ac (160) hhgff 2010-02-07 11:16:41