/*
说到底,还是并查集;
当然这题比较特殊;
*/
一般的并查集应该这么写:
for(int i = 1; i <= m; i++) //######## { scanf("%d%d",&x,&y); Union(x,y); //合并 } //########一般并查集合并的是 两个有关系的;
题目输入的是x y
如果x y 的根都想等,说明他们是同性恋,
如果不相等,则需要合并,
需要合并的是同性的;sex[x] 存储的是:x 的性别相反的 符号;
#include#include #include #include #include #include #include #define maxn 2005int father[maxn],sex[maxn]; using namespace std;int find(int x) //查找根{ if(father[x]==x) return x; else return father[x] = find(father[x]);}void Union(int x, int y) //合并{ int f1 = find(x); int f2 = find(y); if(f1 != f2) father[f1] = f2;}int main(int argc, char *argv[]){ int T,n,m,x,y,Case = 1; scanf("%d",&T); while(T--) { int flag = 0; scanf("%d%d",&n,&m); memset(sex,0,sizeof(sex));//***** for(int i = 1; i <= n; i++) father[i] = i; for(int i = 1; i <= m; i++) { scanf("%d%d",&x,&y); if(flag) continue; if(find(x)==find(y)) //########## { flag = 1; } else { if(sex[x] == 0) sex[x] = y; else Union(sex[x],y); if(sex[y] == 0) sex[y] = x; else Union(sex[y],x); } //########### } if(!flag) { printf("Scenario #%d:\n",Case++); puts("No suspicious bugs found!"); printf("\n"); } else { printf("Scenario #%d:\n",Case++); puts("Suspicious bugs found!"); printf("\n"); } } return 0;}