A Bug's life
pku 2492
一份并查集报告
题目大意是：professor Hopper发现虫子是异性交配，题目给了我们几组数据第一个数是有几组，接下去时两个数，第一个数虫子的个数；第二个是观察到两个虫子是异性的组数；再接下去数相交虫子的号码。。。。。。
输出：
	先输出第几组；
	如果professor Hopper的理论正确输出：No suspicious bugs found!
	否者输出 suspicious bugs found!（就是发现同性恋。。。。。。。）
用并查集（合并和查找元素的方法。。。。。。。其实我一直不是很明白这个方法的意思）
具体步骤：
	
1、构建并查集，father[],sex[];如果节点a1是a2的父节点，且性别相同，则置sex[a2]为false, 否则为true;可以将元素初始化father[i]=i;sex[i]=false;
2、查找元素，如果输入元素a，b有相同的根节点，即在同一集合中，
		如果sex[a]，sex[b]相同，说明a，b相对于他们的根节点的性别相同，即a与b性别相同，这与已知的a，b性别互异矛盾；程序输出			suspicious bugs found!
		否者继续搜；
	    如果输入元素a，b的father不相同，即在不同的集合中，合并两个集合。。。。
3、第三步是最难的，分析题目，解决如何搜，如何合并的事情。。。。。。
	解题思路可能是这样的：对于输入的a，b，搜索a，b的根节点，更新sex和father表，其实就是求出a，b相对于根节点（这里的根节点很重要，他不一定a，b的父亲节点）的性别，如果对根节点的性别相同，输出suspicious bugs found!，否则合并两个个集合，其实就是建立根节点的联系。设c是a的根节点，d是b的根节点，已知a，b是异性，sex[a]记录了a，c之间的关系，sex[b]记录了b，d之间的关系，现在将d连接到c上，求sex[d],
	如果sex[a]=false,sex[b]=false,即a,c的性别相同，b,d的性别相同，那么我们可以知道d，c的性别相反，即sex[d]=true;
	如果sex[a]=false,sex[b]=ture,即a，c的性别相同，b，d的性别不同，那么我们可以知道d，c的性别相同，即sex[d]=false;
	如果sex[a]=ture,sex[b]=false,和第二种情况相同，sex[d]=false;
	如果sex[a]=ture,sex[b]=ture,即a，c的性别相反，c，d的性别相反，那么我们可以知道d，c的性别相反，即sex[d]=ture;
从上面几个如果可以看出sex[d]=!(sex[a]^sex[b])

还有最后一步，怎么求a，b相对与其根节点的sex

设c是b的father，b是a的father，分别有sex[a],sex[b],求sex[a]（a相对c）
	如果sex[a]=false,sex[b]=false,则sex[a]=false;
	如果sex[a]=false,sex[b]=ture,则sex[a]=ture;
	如果sex[a]=ture,sex[b]=false,则sex[a]=ture;
	如果sex[a]=ture,sex[b]=ture,则sex[a]=false;

	
源代码：
#include<cstdio>
#define	M 2003
int father[M];
bool	sex[M];
int Find_Root(int x)//找到根节点，不含路劲压缩  time 1032ms  Accept
{
	bool s=false;
	int r=x;
	while(father[r]!=r)
	{
		s^=sex[r];
		r=father[r];
	}
	sex[x]=s;
	father[x]=r;
	return r;
}

int Find_Root(int x)//压缩路劲，将所有x路劲上的节点连到根节点上，更新sex表，返回根节点time 985 Accept
{
	bool s=false;
	int r=x;
	int t_father;
	while(father[r]!=r)
	{
		s^=sex[r];
		r=father[r];
	}
	t_father=father[x];
	while(t_father!=r)
	{
	sex[x]=s;
	father[x]=r;
	s^=sex[t_father];
	t_father=father[x];
	x=t_father;
	}
	return r;
}
两个函数任选一个。。。。。。
int main()
{
	int a,b,i,j,n,m,k,root_a,root_b,l;
	scanf("%d",&k);
	for(i=0;i<k;i++)
	{
		bool flag=true;
		scanf("%d %d",&n,&m);
		for(l=0;l<=n;l++)
		{
			father[l]=l;
			sex[l]=false;//自己和自己性别当然相同。。。
		}
		for(j=0;j<m;j++)
		{
			scanf("%d",&a);
			scanf("%d",&b);
			if(flag)
			{
				root_a=Find_Root(a);
				root_b=Find_Root(b);
				if(root_a==root_b)
				{
					flag=sex[a]^sex[b];
				}
				else
				{
					father[root_a]=root_b;
					sex[root_a]=!(sex[a]^sex[b]);
				}
			}
		}
		printf("Scenario #%d:\n",i+1);
		if(flag)
			printf("No suspicious bugs found!\n\n");
		else
			printf("Suspicious bugs found!\n\n");
	}
	return 0;
}

看了两天，才明白。。。。。。。。很水，很可怜！

• Re:解题报告。。。 (3012) huicpc0838 2010-05-04 15:34:00