Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14610 Accepted Submission(s): 4771
#include <stdio.h> //存储的是其父亲的下表 int bugs[2010]; int relation[2010];//1:相同性别 0:不同性别 //初始化 void init(int len) { for(int i = 0;i <= len; i++) { bugs[i] = i; relation[i] = 1; } } //找到根 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]+1)%2; 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])%2; } int main() { int S; int n,inter; int bug1,bug2,parent1,parent2; bool flag;//false:无同性恋,true:有同性恋 scanf("%d",&S); for(int i=1; i<=S;i++) { scanf("%d%d",&n,&inter); flag = false; init(n);//初始化,使其父节点为自己 for(int j = 1; 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 0; }
原文:http://www.cnblogs.com/l609929321/p/6567398.html