本文共 3502 字，大约阅读时间需要 11 分钟。
1、题目大意：给定一些关系，判断是不是存在同性恋的关系，比如说关系是：
1 2
2 3 1 3结果会输出存在同性恋关系，因为12说明12是异性，23说明23是异性，则可以推出13是同性，而下一行13说明13是异性，相矛盾，所有输出对教授的研究存在怀疑
2、思路：
if（fx==fy)
说明x和y具有相同的父节点，即属于同一个集合，则可以断定是同性恋，
else
稍麻烦些，用sex【a】数组记录a是否有异性朋友，如果没有则输入的b则是a的异性朋友，否则，merge（sex[a],b);
3/题目：
A Bug's Life Time Limit : 15000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)Total Submission(s) : 14 Accepted Submission(s) : 3Problem Description Background Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs. Problem Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it. Input The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one. Output The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong. Sample Input23 31 22 31 34 21 23 4 Sample OutputScenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!HintHuge input,scanf is recommended. Source TUD Programming Contest 2005, Darmstadt, Germany
4、代码：
#include#include int set[2005];int sex[2005];int find(int x){ int r=x; while(r!=set[r]) r=set[r]; int i=x; while(i!=r) { int j=set[i]; set[i]=r; i=j; } return r;}void merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) set[fx]=fy;}int main(){ int cases,n,m,a,b,t=1; scanf("%d",&cases); while(cases--) { printf("Scenario #%d:\n",t++); scanf("%d%d",&n,&m); memset(sex,0,sizeof(sex)); int flag=0; for(int i=1;i<=n;i++) { set[i]=i; } for(int i=1; i<=m; i++) { scanf("%d%d",&a,&b);//第一遍错了，错在将此句话放在了if后边，一旦flag==1后， //continue,将跳出本次循环，scanf将不能继续读入 if(flag==1) continue; int fx=find(a); int fy=find(b); if(fx==fy) { flag=1; continue; } else { if(sex[a]==0)//a没有喜欢的人，即没有异性朋友，则b作为a的异性朋友 sex[a]=b; else//如果a有喜欢的人，那么a喜欢的人也将是b喜欢的人，即sex[a]和b合并 merge(sex[a],b); if(sex[b]==0) sex[b]=a; else merge(sex[b],a); } } /*for(int i=1;i<=n;i++) printf("sex[%d]=%d ",i,set[i]); printf("\n");*/ if(flag==1) printf("Suspicious bugs found!\n\n");//注意输出，有空行 else printf("No suspicious bugs found!\n\n"); } return 0;}/*23 31 22 31 34 21 23 4*//*24 41 22 32 43 45 31 42 34 5*/
转载地址：http://oycdi.baihongyu.com/