> 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;
> }
> 
> 看了两天，才明白。。。。。。。。很水，很可怜！
> 


很好很强大，顶！