hdu-1325 Is It A Tree?---并查集

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1325

题目大意：

给出n条有向边，判断是不是一棵树。

解题思路：

和hdu-1272类似，是它的进阶版本，不同之处是本题为有向边。

有向边的话，只能用并查集的方法，因为是有向边，不能确定根节点的位置（网上有记录每个点的入度的做法，可以直接记录度数求解，根节点入度为0，但此处只用并查集求解）

因为是有向边，在使用并查集的时候，有向边<x, y>记录为p[y] = x，记录y的父节点为x，不过在记录之前判断是否有环。最终只要每个点的根节点为同一个数，且满足点数=边数+1，那么就是一颗有向边构成的树了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T, n, m;
 4 const int maxn = 100000 + 10;
 5 int cases;
 6 int p[maxn];
 7 void init()
 8 {
 9     for(int i = 0; i < maxn; i++)p[i] = i;
10 }
11 int Find(int x)
12 {
13     return x == p[x] ? x : p[x] = Find(p[x]);
14 }
15 int main()
16 {
17     int x, y, c;
18     while(cin >> x >> y && (x + y >= 0))
19     {
20         m = 1;
21         n = 0;
22         set<int>s;
23         s.insert(x);
24         s.insert(y);
25         if(x == 0 && y == 0)//0 0 的特判
26         {
27             cout<<"Case "<<++cases<<" is a tree."<<endl;
28             continue;
29         }
30         init();
31         int flag = 1;
32         p[y] = x;//最开始的边
33         if(x == y)flag = 0;
34         while(cin >> x >> y && (x + y))
35         {
36             s.insert(x);
37             s.insert(y);
38             m++;
39             if(Find(x) == Find(y))//判断是否存在环
40             {
41                 flag = 0;
42             }
43             p[y] = Find(x);//有向边的写法
44         }
45         set<int>::iterator it = s.begin();
46         int t = Find(*it);
47         for(; flag && it != s.end(); it++)
48         {
49             if(Find(*it) != t)flag = 0;
50         }
51         if(s.size() == m + 1 && flag)cout<<"Case "<<++cases<<" is a tree."<<endl;
52         else cout<<"Case "<<++cases<<" is not a tree."<<endl;
53     }
54     return 0;
55 }