hdu1829 参考答案

   1 /*
   2 hdu 1829 并查集 二分图判定
   3 ymc 2008/10/29
   4 题目大意：
   5 有n只虫子，分为公母两种性别。
   6 给定m对虫子的相互恋爱关系，判定有没有同性恋虫子存在。
   7 解题思路：
   8 用opp[i]记录与i异性的虫子的id，如果没有，则为0。
   9 已经知道同性的虫子在一个集合中，用p[i]表示i虫子在这个
  10 集合中的父节点。
  11 初始p[i]=0,opp[i]=0。
  12 对每一对关系x，y。
  13 先求x,y的根节点rx，ry。
  14 若rx==ry,则说明存在同性恋。
  15 若rx！=ry，合并x，opp[y],合并opp[x],y。
  16 若opp[x]==0,直接opp[x]=y。
  17 */
  18 #include <iostream>
  19 using namespace std;
  20 const int N=2010;
  21 int p[N];
  22 int opp[N];
  23 int n,m;
  24 bool ans;
  25 int FindRoot(int x)
  26 {
  27     int rx=x;
  28     while(p[rx]!=0)
  29         rx=p[rx];
  30     int tx=x;
  31     int tmp;
  32     while(p[tx]!=0)
  33     {
  34         tmp=p[tx];
  35         p[tx]=rx;
  36         tx=tmp;
  37     }
  38     return rx;
  39 }
  40 void Merge(int x,int y)
  41 {
  42     int rx,ry;
  43     rx=FindRoot(x);
  44     ry=FindRoot(y);
  45     if(rx!=ry)
  46         p[ry]=rx;
  47 }
  48 void Solve()
  49 {
  50     int x,y;
  51     ans=true;
  52     memset(p,0,sizeof(p));
  53     memset(opp,0,sizeof(opp));
  54     scanf("%d %d",&n,&m);
  55     int rx,ry;
  56     for(int i=0;i<m;i++)
  57     {
  58         scanf("%d %d",&x,&y);
  59         if(ans==false)
  60             continue;
  61         rx=FindRoot(x);
  62         ry=FindRoot(y);
  63         if(rx==ry)//同性恋
  64         {
  65             ans=false;
  66             continue;
  67         }
  68         if(opp[x]==0)//合并opp[x]与y
  69             opp[x]=y;
  70         else
  71             Merge(opp[x],y);
  72         if(opp[y]==0)//合并opp[y]与x
  73             opp[y]=x;
  74         else
  75             Merge(x,opp[y]);
  76     }
  77 }
  78 int main()
  79 {
  80     int test;
  81     scanf("%d",&test);
  82     for(int t=1;t<=test;t++)
  83     {
  84         Solve();
  85         printf("Scenario #%d:\n",t);
  86         if(ans)
  87             printf("No suspicious bugs found!\n\n");
  88         else
  89             printf("Suspicious bugs found!\n\n");
  90 
  91     }
  92 }