poj1308 Is It A Tree?（並查集）詳解，poj1308tree
poj1308 http://poj.org/problem?id=1308
題目大意：輸入若干組測試數據，輸入 （-1 -1） 時輸入結束。每組測試數據以輸入（0 0）為結束標志。然後根據所給的所有（父親， 孩子）數據對判斷 是否能構成一棵樹。
分析： 都以了解樹只有一個根節點，那麼我們就判斷是不是有多個樹；又知道每個節點只有一個父親節點，那麼我們就判斷他是不是構成環，成環則不是樹。
注意： ①可以是空樹； ②所給的節點構成森林（多個樹）是不可以的，必須只能構成一棵樹。
![]()
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int out, flag, x, y, num, pre[10010];
int find(int a)//查找根節點
{
int r, i, j;
r = a; i = a;
while(pre[r] != r)
r = pre[r];
while(pre[i] != r)
{
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
int main()
{
num = 0; out = 1;
while(out)
{
//先對所有節點的根節點進行初始化
for(int i = 1; i <= 10000; i++)
pre[i] = i;
flag = 1;
while(scanf("%d%d", &x, &y))
{
if(x == 0 && y == 0)
break;
else if(x == -1 && y == -1)
{
out = 0;
break;
}
int fx = find(x);
int fy = find(y);
//此處我們判斷是否構成環
//如果x和y的根節點相同，那麼他們已經是屬於同一棵樹
//若x又是y的父親節點，那麼將構成環
if(fx == fy)
flag = 0;
//如果x和y根節點不同，即不屬於同一棵樹， 那麼將其合並成一棵樹
else if(fx != fy)
pre[fy] = fx;
}
int k = 0;
//此處我們判斷是不是森林，對所有節點(不包括沒涉及的點)的根節點
//進行統計，若不都一樣那麼說明存在多個跟， 有多顆樹， 否則是一棵樹。
for(int i = 1; i <= 10000; i++)
{
int ans = find(i);
if(ans != i && k == 0)
k = ans;
else if(k != 0 && ans != i)
{
if(ans != k)
flag = 0;
}
}
if(out == 1 && flag == 0)
printf("Case %d is not a tree.\n", ++num);
else if(out == 1 && flag == 1)
printf("Case %d is a tree.\n", ++num);
}
return 0;
}
View Code
杭電的1272 和這個題差不多 稍微改改就可以了。
![]()
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int out, flag, x, y, pre[100010];
int find(int a)
{
int r, i, j;
r = a; i = a;
while(pre[r] != r)
r = pre[r];
while(pre[i] != r)
{
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
int main()
{
out = 1;
while(out)
{
for(int i = 1; i <= 100000; i++)
{
pre[i] = i;
}
flag = 1;
while(scanf("%d%d", &x, &y))
{
if(x == 0 && y == 0)
break;
else if(x == -1 && y == -1)
{
out = 0;
break;
}
int fx = find(x);
int fy = find(y);
if(fx != fy)
{
pre[fx] = fy;
}
else if(fx == fy)
{
flag = 0;
}
}
int k = 0;
for(int i = 1; i <= 100000; i++)
{
int ans = find(i);
if(ans != i && k == 0)
k = ans;
else if(k != 0 && ans != i)
{
if(ans != k)
flag = 0;
}
}
if(out == 1 && flag == 0)
printf("No\n");
else if(out == 1 && flag == 1)
printf("Yes\n");
}
return 0;
}
View Code
