题目链接:http://172.16.200.33/JudgeOnline/problem.php?id=1003
分析:
(1)题意很简单,就是检查一堆数据中是否有同性恋,找出主要矛盾是如果1喜欢2,2喜欢3,而1又喜欢3,则矛盾。找出出现类的的矛盾
(2)这里用bugs数组存储其父亲节点的下标,用sex数组存储该虫子与根节点之间的关系。1为同性,0为异性。
(3)并查集详见注释(借鉴大神的思路,很好)
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define M 2005
int sex[M],bugs[M];
void init(int n) //初始化
{
for(int i=;i<=n;i++)
{
bugs[i]=i;
sex[i]=;
}
}
int find(int bug) //打根
{
if(bugs[bug]==bug) return bug;
int temp=bugs[bug];//递归更新域,返回最终的父亲节点,把所有的孩子都更新了
//注意这里,求当前位置和父亲的关系,记录之前父亲的位置为tem,然后因为是递归,
//此时的sex[temp]已经在递归中更新过了,也就是孩子和父亲的关系+父亲和爷爷的关系+1然后模2就得到
//孩子和爷爷的关系,这里用0和1表示,0表示不同性别,1表示相同性别
bugs[bug]=find(bugs[bug]);
sex[bug]=(sex[bug]+sex[temp]+)%;
return bugs[bug];
}
void union_set(int a,int b,int x,int y)
{//合并,让前边的集合的根指向后边集合的根,成为一个集合
bugs[x]=y;//更新前边集合根和新的集合根之间的关系,
//注意这里,sex[a]+sex[x]与sex[b]
//相对于新的父节点必须相差1个等级,因为他们不是gay
sex[x]=(sex[b]-sex[a])%;
}
int main()
{
int n,m,t;
scanf("%d",&t);
for(int ca=;ca<=t;ca++)
{
if(ca>=) printf("\n");
scanf("%d %d",&n,&m);
init(n);//初始化,使其父节点为自己
bool f=false;//false:无同性恋,true:有同性恋
for(int i=;i<=m;i++)
{
int bug1,bug2;
scanf("%d %d",&bug1,&bug2);
if(f) continue;
int par1=find(bug1);
int par2=find(bug2);
if(par1==par2&&sex[par1]==sex[par2]) f=true; //同性
union_set(bug1,bug2,par1,par2);
}
if(f) printf("Scenario #%d:\nSuspicious bugs found!\n",ca);
else printf("Scenario #%d:\nNo suspicious bugs found!\n",ca);
}
return ;
}