题目意思：给定一系列数对，例如a和b，表示a和b不是同一种性别，然后不断的给出这样的数对，问有没有性别不对的情况。
例如给定：
1 2
3 4
1 3
那这里就是说1和2不是同种性别，3和4也不是同种性别，1和3不是同种性别，那这样就说明1和3是同一种性别，2和4是同一种性别，所以没有任何歧义，这时候输出No suspicious bugs found!。
但是例如
1 2
2 3
1 3
1和2不同性别，2和3不同性别，那么1和3同一性别的，但是第三组数对又表明1和3不同性别，所以这里就出现了3或者1的性别出现了歧义，也就是说条件矛盾，这时候输出Suspicious bugs found!.
这道题一开始的想法是构一张图，判断这个无向图中是否存在环。如果存在环，则说明存在同性的，否则不存在。这里用到了一个公式：无向图中，如果 边数+连通分量数>顶点数，则存在环，否则不存在。
一开始没有对bfs做优化处理，所以超内存了。做了处理之后wa掉了。。。稍微想想就知道是边的数目问题，因为这个是当做无向图处理的，所以在输入时，同一条边可能输入了两次，例如输入1 3和3 1应该是同一条边。所以还要做额外的处理。
做了处理之后还是wa。参考网上的代码，没有一个是思路和我一样的。当时确实没有想到是分组并查集。这里先附上错误的代码。
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"cmath"
#include"string.h"
#include"string"
#include"queue"
using namespace std;
bool flag;
int num_e,num_v,num_p,nume;
bool visited[];
bool judge[][];
struct node
{
int data;
node *next;
};
struct Head
{
node *first;
};
Head head[]; void init()
{
for(int i=;i<=num_v;i++)
{
head[i].first=NULL;
}
} void creat(int fa,int son)//利用邻接表构图
{
node *temp=new node;
temp->data=son;
temp->next=head[fa].first;
head[fa].first=temp;
} void bfs(int i)//利用bfs把同一个连通分量中的点标记起来，从而判断连通分量的个数
{
queue<int>q;
while(!q.empty()) q.pop();
q.push(i);
int cur;
node *temp=new node;
while(!q.empty())
{
cur=q.front();
q.pop();
temp=head[cur].first;
while(temp!=NULL)
{
if(!visited[temp->data])
{
visited[temp->data]=true;
q.push(temp->data);
}
temp=temp->next;
}
}
} int main()
{
int case_count,case_num;
int bug1,bug2;
scanf("%d",&case_num);
for(case_count=;case_count<=case_num;case_count++)
{
num_p=;
nume=;
memset(visited,false,sizeof(visited));//用于标记点是否被访问过
memset(judge,false,sizeof(judge));//用于标记边是否重复
flag=false;
scanf("%d%d",&num_v,&num_e);
init();
for(int i=;i<num_e;i++)
{
scanf("%d%d",&bug1,&bug2);
if(!judge[bug1][bug2])
{
judge[bug1][bug2]=judge[bug2][bug1]=true;
creat(bug1,bug2);
}
else
nume++;
}
num_e-=nume;//实际边的数目
cout<<"Scenario #"<<case_count<<":"<<endl;
for(int i=;i<=num_v;i++)
{
if(!visited[i])
{
visited[i]=true;
num_p++;
bfs(i);
}
}
cout<<num_p<<" "<<num_e<<" "<<num_v<<endl;
if(num_p+num_e>num_v) flag=true;//判断原图中是否存在环
if(flag)
cout<<"Suspicious bugs found!"<<endl;
else
cout<<"No suspicious bugs found!"<<endl;
cout<<endl;
}
return ;
}
看了别人的思路，感觉似乎自己一开始想的就是错的。这题好像没有判断无向图有没有环这么简单。。。但是我也找不出其他的反例。感觉如果存在同性，必然是无向图中存在环。当然，如果无向图中存在环，必然存在同性。
#include <stdio.h>
//存储的是其父亲的下表
int bugs[];
int relation[];//1:相同性别 0：不同性别
//初始化
void init(int len)
{
for(int i = ;i <= len; i++)
{
bugs[i] = i;
relation[i] = ;
}
}
//找到根
int find(int bug)
{
if(bugs[bug]==bug)return bug;
int tem = bugs[bug];
bugs[bug] = find(bugs[bug]);
//递归更新域，返回最终的父亲节点，把所有的孩子都更新了
//注意这里，求当前位置和父亲的关系，记录之前父亲的位置为tem,然后因为是递归，
//此时的relation[tem]已经在递归中更新过了，也就是孩子和父亲的关系+父亲和爷爷的关系+1然后模2就得到
//孩子和爷爷的关系，这里用0和1表示，0表示不同性别，1表示相同性别
relation[bug] = (relation[bug]+relation[tem]+)%;
return bugs[bug];
} void union_set(int a,int b,int x,int y)
{
//合并，让前边的集合的根指向后边集合的根，成为一个集合
bugs[x]=y;
//更新前边集合根和新的集合根之间的关系，
//注意这里，relation[a]+relation[x]与relation[b]
//相对于新的父节点必须相差1个等级，因为他们不是gay
relation[x] = (relation[b]-relation[a])%;
} int main()
{
int S;
int n,inter;
int bug1,bug2,parent1,parent2;
bool flag;//false:无同性恋，true：有同性恋
scanf("%d",&S);
for(int i=; i<=S;i++)
{
scanf("%d%d",&n,&inter);
flag = false;
init(n);//初始化，使其父节点为自己
for(int j = ; j <= inter; j++)
{
scanf("%d%d",&bug1,&bug2);
if(flag)continue;
parent1 = find(bug1);
parent2 = find(bug2);
if(parent1==parent2)
{
if(relation[bug1]==relation[bug2])//同性
flag = true;
}
union_set(bug1,bug2,parent1,parent2);
}
if(flag)
printf("Scenario #%d:\nSuspicious bugs found!\n",i);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n",i);
printf("\n");
}
return ;
}