最近几天有点忙，敲代码敲的比较少，才几天就比较生疏了。昨天晚上做了这道题和杭电的1225，终于找回了

感觉。但是遗憾的是杭电那道题没有A掉，找不出错在哪。先说POJ1308，这道题要求我们判断这些case的数字

连接起来是否构成一棵树。一棵树只有一个树根，树当中的两个父节点不能含有相同的儿子。然后我就开始写

了，用的依然是并查集，但是看了下数据感觉不好输入，-1，-1是结束输入，0，0是结束一个case，所以每

个case开始的第一组数据单独输入，后面的数据用while循环判断是否是0，0来输入。问题依然有，不知道哪些

树出现了，所以增加了一个标记数组，貌似这是第一次用布尔数...

下面是代码：

 

#include
     
       using namespace std; const int N = 105; int p[N]; bool flag[N]; void make_set(void) {
   for(int i = 0; i < 105; i++)     {
           p[i] = i;         flag[i] = false;     } } int find_set(int x){
   return p[x] == x ? x : (p[x] = find_set(p[x])); } void union_set(int x, int y){
       x = find_set(x);     y = find_set(y); if(x == y) return;     p[y] = x; } int main(){
   int x, y, t = 1, first; while(scanf("%d %d", &x, &y) != EOF){
   if(x == -1 && y == -1) break; if(x == 0 && y == 0){        // 1.空树也是树，果断坑爹了             printf("Case %d is a tree.\n", t ++); continue;         }         make_set();         flag[x] = flag[y] = true;         first = x; bool tree = true; if(x == y) tree = false;    //  两个数相等表示同一点指向自己，不是树，同第2点 else union_set(x, y); while(scanf("%d %d", &x, &y) && x != 0){
               flag[x] = flag[y] = true; if(find_set(x) == find_set(y)) tree = false;   // 2.两个数的树根相同 //但再次将y指向了x，重复指向也不是树             union_set(x, y);//合并         } for(int i = 1; i < 105; i ++)   //3.最后只能有一个树根，多个树根为森林             if(flag[i] && find_set(i) != find_set(first)) {
                   tree = false; break;             } if(tree) printf("Case %d is a tree.\n", t ++); else printf("Case %d is not a tree.\n", t ++);     } return 0; }
     

 

下一步还是继续做并查集，然后最小生成树，最短路径。