hdoj1325 Is It A Tree?，hdoj1325tree
Is It A Tree?題目鏈接
題意：
多組測試數據， 每組數據有多個數對， 表示一條有向邊（即第一個數是第二個數的父節點）， 以 0,0 為一組測試數據結束標志。當輸入-1，-1時測試結束。 從那些給出的信息中判斷是否是一棵樹。
分析：
1、只可以有一個根節點， 也可以是一個點都沒有的空樹；
2、除了根節點， 每個點只有一個父節點。
3、因為只可以有一個父節點， 所以我們可以把一個合法的關系對（一個父親節點與孩子節點對）合並到一個集合裡， 他們的父節點都標記為所屬樹的根節點， 那樣我們方便判斷是否成環。
4、判斷是否成環， 成環不可以。
5、 還有一個很衰的地方， 注意不光輸入-1，-1 測試結束， 只要輸入兩個數都小於0就結束。
![]()
#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N = 10005;
int a, b, n, mi, mx, sum, flag, v[N], pre[N];
int find(int x)//尋找x所屬的樹的根節點
{
int r, i, j;
r = x; i = x;
while(r != pre[r])
r = pre[r];
while(pre[i] != r)
{
j = pre[i];
pre[i] = r;
i = j;
}
return pre[x];
}
int main()
{
n = 0;
while(scanf("%d%d", &a, &b) != EOF)
{
memset(v, 0, sizeof(v));//記錄所涉及的點
for(int i = 1; i <= N; i++)
pre[i] = i;
if(a < 0 && b < 0) break;
else if(a == 0 && b == 0)//特殊處理， 空樹
{
printf("Case %d is a tree.\n", ++n);
continue;
}
pre[b] = a;
v[a] = 1;
v[b] = 1;
mi = min(a, b);
mx = max(a, b);
flag = 1;
while(scanf("%d%d", &a, &b) != EOF)
{
if(a == 0 && b == 0) break;
if(mx < a || mx < b) mx = max(a, b);
if(mi > a || mi > b) mi = min(a, b);
v[a] = 1;
v[b] = 1;
if(flag == 1)
{
int fx = find(a);
int fy = find(b);
if((fy != b) || (fy == fx))//若構成環， 或孩子節點已經有父節點了， 那就是不合法的邊
flag = 0;
else if(fy == b && fy != fx)//如果不構成環並且沒有父親節點， 那就是合法的， 加入
pre[b] = fx;
}
}
int sum = 0;
if(flag == 1)
{
for(int i = mi; i <= mx; i++)//判斷是否存在多棵樹
{
if(v[i] == 1)
{
int fx = find(i);
if(fx == i)
{
sum++;
if(sum > 1)
{
flag = 0;
break;
}
}
}
}
}
if(flag == 1)
printf("Case %d is a tree.\n", ++n);
else if(flag == 0)
printf("Case %d is not a tree.\n", ++n);
}
return 0;
}
View Code
