hdu1272 参考答案

   1 //这道题我做了很长时间,主要是概念没搞清,题目题意也不清晰,一系列原因导致做题时间过长。
   2 //下面我介绍一下题目思路:
   3 //本题主要是并查集的回路判断(根节点是否相同)和以及分支数(判断根节点数)的判断,其他的并查集的基本
   4 //例程还是必须的,比如路径压缩。
   5 //下面是一段难看的代码,随便看看……,有好看的代码积极上传:)
   6 
   7 #include<iostream>
   8 #define N 100100
   9 using namespace std;
  10 
  11 int p[N];
  12 int ex[N];//设一个数组,记录输入数有多少
  13 
  14 bool isLegal(int x, int y)
  15 {
  16         int tx,ty;
  17         int mx,my;
  18         int t;
  19 
  20         tx = x;
  21         ty = y;
  22 
  23         while(p[tx])
  24                 tx = p[tx];
  25 
  26         while(p[ty])
  27                 ty = p[ty];
  28 
  29         if( tx == ty)
  30                 return false;   
  31 
  32         mx = x;
  33         my = y;
  34         while(p[mx])
  35         {
  36                 t = p[mx];
  37                 p[mx] = tx;
  38                 mx = t;
  39         }
  40         while(p[my])
  41         {
  42                 t = p[my];
  43                 p[my] = ty;
  44                 my = t; 
  45         }
  46         p[tx] = ty;
  47         return true;
  48 }
  49 
  50 int main()
  51 {
  52         int x,y;
  53         int a,max;//max主要是设置一个界,对树的分支数判断时遍历数组的上界,a是记录第一个是根节点的元素(一个分支一个根节点)
  54         bool no = false;
  55         memset(p,0,sizeof(p));
  56         while(scanf("%d%d",&x,&y)!=EOF)
  57         {
  58                 max = max<x?x:max;
  59                 max = max<y?y:max;
  60                 if(x == y && x == -1)
  61                         exit(0);
  62                 else if(x== y && x == 0)
  63                 {
  64                         if(no)
  65                         {
  66                                 printf("No\n");
  67                                 no = false;
  68                         }
  69                         else
  70                         {
  71                                 for(int i = 1; i <= max; i++)
  72                                         if(!p[i] && ex[i] == 1)
  73                                         {
  74                                                 a = i;
  75                                                 break;
  76                                         }
  77 
  78                                 for(; i <= max; i++)
  79                                         if( (!p[i]) && (i != a) && (ex[i] == 1) )
  80                                         {
  81                                                 printf("No\n");
  82                                                 no = true;
  83                                                 break;
  84                                         }
  85                                 if(!no)
  86                                         printf("Yes\n");
  87                         }
  88                         memset(p,0,sizeof(p));
  89                         memset(ex,0,sizeof(ex));
  90                         max = -1;
  91                         no = false;
  92                 
  93                 }
  94                 else
  95                 {
  96                         ex[x] = 1;
  97                         ex[y] = 1;
  98                         if(!isLegal(x,y))
  99                                 no = true;
 100                 }       
 101         }
 102         return 0;
 103 }
 104 
 105 //ASUN……
 106 

hdu1272 参考答案 (2008-11-05 17:49:56由218编辑)