HDU 1325，POJ 1308 Is It A Tree

HDU認為1>2,3>2不是樹，POJ認為是，

而Virtual Judge上引用的是POJ數據

這就是唯一的區別....(因為這個瞎折騰了半天)

此題因為是為了熟悉並查集而刷，其實想了下其實好好利用sort應該能更簡單A掉，下次有空再去試試...

題目大意：判斷是否為樹，so：

1，無環；

2，除了根，所有的入度為1，根入度為0；

3，這個結構只有一個根，不然是森林了；4.空樹也是樹，即第一次輸入的兩個數字為0 0則是樹，其他時候輸入只是結束條件

因為POJ和HDU題面一樣，要求不一樣，所以這題解法唯一區別就是

HDU上用所有節點的總父節點唯一判斷，而POJ則每輸入兩個數，判

斷他們總父節點是否相等，相等則成環了.

hdu AC代碼：http://paste.ubuntu.com/25081598/POJ AC代碼：http://paste.ubuntu.com/25081600/

下面貼的是POJ上AC的代碼：

//Is It A Tree?
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 1005
int pre[maxn],visB[maxn],root,vis[maxn],MAX,flag=0;
void iint
{
for(int i=0; i<=maxn; i++) { pre[i]=i; visB[i]=0; vis[i]=0; } MAX=0; flag=0; } int find(int x) { return x==pre[x]?x:find(pre[x]); } void join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; } int main { int a,b,Case=1/*,real_flag1=0*/,FLAG=0; iint; while(~scanf("%d%d",&a,&b),a>=0&&b>=0)
{
if(a==0&&b==0&&flag==0)
{ //空樹也是樹
printf("Case %d is a tree.
",Case++);
iint;
continue;
}
flag=1;
visB[b]++;
vis[a]=vis[b]=1;

MAX=max(MAX,a); MAX=max(MAX,b);
/*for(int i=1; i<=MAX; i++) { if(vis[i]&&visB[i]>1) real_flag1=1;
//判斷根節點是否都有且只有一次，或者說父節點只有一個
if(vis[i]&&visB[i]==0) real_flag2++;
//非環時，最高父節點不會被指向，所以不被指的有且只有1個
//POJ會WA可能是，如3->1 2->1都算一個樹了，2333
}*/
/*if(real_flag1) FLAG=1;*/ //天真

if(find(a)==find(b)&&a!=0&&b!=0) FLAG=1;
記住：1->2 ,3->2時候也是樹，所以判斷是否為環，直接在每次讀 入兩個數字時候看它們的最高父節點是否相等，相等澤成環，比如
1->2,2->3,3>1.

join(a,b);

if(a==0&&b==0)
{
int ans=0;
for(int i=1; i<=MAX; i++) if(vis[i]&&pre[i]==i) ans++; if(ans!=1||FLAG) printf("Case %d is not a tree. ",Case++); else printf("Case %d is a tree. ",Case++); iint; /*real_flag1=0;*/ FLAG=0; continue; } } return 0; }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！