POJ-1308-Is It A Tree? 解题报告

这是一道并查集类型的题目，较容易。题意是说给定每个互相连接的节点的编号，判断这些节点是否能够形成树形结构并按题目要求根据情况进行输出。满足树形结构的要求是

1）只有一个根节点，也就是说这个根节点没有父节点（或者说父节点指向自己）；

2）根节点以外的每个节点有且只有一个父节点（当然每个节点可有多个子节点）；

3）从根节点到达其他任意一个节点有且只有一条路线（解释的更简单些就是这些节点不能够产生环）；

注意：这道题有些特殊情况还是有点令人想不到的，比如直接输入0 0的话，是一个空树，按照满足树形结构的要求来输出，还有就是如果输入的数据有多个树形结构（也就是森林），按照不满足树形结构的要求来输出。

接下来讲解题思路，用并查集实现这道题，当输入的两个节点不属于同一个结构时（也就是没有共同的根节点），将这两个节点进行合并操作，而如果输入的两个节点属于同一结构时（有同一个根节点），说明这个结构产生了环，那么这个结构肯定不属于树形结构。

输入0 0时代表这个结构输入结束，如果只输入了0 0可以做特殊判断解决。现在讲讲如果出现了森林应该如何解决。首先要知道一个树形结构的节点数n与边数s的关系显然是n = s + 1，因为不出现环结构。我们在输入时记录节点数以及边数，最后输出的时候判断节点数与边数是否满足这个公式就ok了。

下面是我的解题代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define N 50001
  4 
  5 int bleg[N];        /*存储父节点*/
  6 int number = 1;     /*case数*/
  7 int ferr = 0;       /*标志变量，1代表非树形结构*/
  8 int num[2*N];       /*存储节点的编号*/
  9 int n = 0;          /*表示num数组存储节点的数量*/
 10 int side = 0;       /*边的数量*/
 11 char *it = "is a tree.";
 12 char *nt = "is not a tree.";
 13 
 14 
 15 void Init();    /*初始化*/
 16 
 17 int Find(int x);    /*查找操作*/
 18 
 19 void Union(int x, int y);   /*合并操作*/
 20 
 21 void Judge();   /*判断节点数与边数是否满足树形结构的公式*/
 22 
 23 int Mycompare(const void *a, const void *b);    /*qsort函数的比较函数*/
 24 
 25 int main()
 26 {
 27     int x, y;
 28     Init();
 29     while (~scanf("%d %d", &x, &y))
 30     {
 31         if (x == y && x == 0)
 32         {
 33             Judge();        /*判断*/
 34             if (ferr == 1)
 35             {
 36                 printf("Case %d %s
", number++, nt);
 37             }
 38             else
 39             {
 40                 printf("Case %d %s
", number++, it);
 41             }
 42             Init();         /*初始化*/
 43         }
 44         else if (x == y && x == -1)
 45         {
 46             break;
 47         }
 48         else
 49         {
 50             num[n++] = x;   /*将两个节点存入数组num*/
 51             num[n++] = y;
 52             if (Find(x) == Find(y)) /*构成环结构*/
 53             {
 54                 ferr = 1;
 55                 continue;
 56             }
 57             else
 58             {
 59                 side++;
 60                 Union(x, y);
 61             }
 62         }
 63     }
 64     return 0;
 65 }
 66 
 67 void Init()
 68 {
 69     int i;
 70     for (i=1; i<N; i++)
 71     {
 72         bleg[i] = i;
 73     }
 74     for (i=0; i<2*N; i++)
 75     {
 76         num[i] = 0;
 77     }
 78     ferr = 0;   /*初始化标记变量*/
 79     side = 0;   /*初始化树形结构的边数*/
 80     n = 0;      /*初始化num数组存储的节点数*/
 81     return;
 82 }
 83 
 84 int Find(int x)     /*查找操作*/
 85 {
 86     int y = bleg[x];
 87     int z;
 88     while (y != bleg[y])
 89     {
 90         y = bleg[y];
 91     }
 92     while (x != bleg[x])    /*路径压缩*/
 93     {
 94         z = bleg[x];
 95         bleg[x] = y;
 96         x = z;
 97     }
 98     return y;
 99 }
100 
101 void Union(int x, int y)    /*合并操作*/
102 {
103     int fx = Find(x);
104     int fy = Find(y);
105     bleg[fx] = fy;
106     return;
107 }
108 
109 void Judge()        /*判断节点数与边数是否满足树形结构的公式*/
110 {
111     int i;
112     int x = num[0];
113     int kind = 1;       /*种类数，因为存储的节点编号会有重复*/
114     qsort(num, n, sizeof(int), Mycompare);      /*先给这些节点编号排序*/
115     for (i=1; i<n; i++)
116     {
117         if (num[i] != x)
118         {
119             x = num[i];
120             kind++;
121         }
122     }
123     if (kind != side + 1)   /*不满足树形结构的边与点公式*/
124     {
125         ferr = 1;
126     }
127     return;
128 }
129 
130 int Mycompare(const void *a, const void *b)     /*qsort函数的比较函数*/
131 {
132     return (*(int *)a - *(int *)b);
133 }