圖論500題——POJ_P1308 Is_It_A _tree？

題目：

Is It A Tree?

Time Limit: 1000MS Memory Limit: 10000K

Total Submissions: 33009 Accepted: 11196

Description

A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. 

There is exactly one node, called the root, to which no directed edges point. 
Every node except the root has exactly one edge pointing to it. There is a unique sequence of directed edges from the root to each node. For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not. 


In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
           

Input

The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.
           

Output

For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).
           

Sample Input

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1
           

Sample Output

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
           

Source

North Central North America 1997

測評網址：戳我通路

所屬專欄：戳我通路

因為題目是英文的，是以這裡大概的翻譯一下：給出幾條邊，判斷這能不能組成是不是一棵樹。

在題目裡有一點值得注意的是，題目是讓你求這是不是一顆數，而不是森林，我就是因為沒有考慮到這一點,是以WA了無數次。

這題可以直接用并查集來做這道題，不過要有一點小小的改動，就是把原來的father[i] = i，改成father[i] = -1，如果有用到在把他的father變成他自己，作用在于，題目的測試樣例是可以跳躍節點的，也就是說，如果這個節點沒有用到，那麼就可以直接忽略這個節點，這也是此題的幾個坑點，不過第二個坑點隻要看樣例輸出就可以了。

然後再講一講此題的思路，先用一個并查集，來判斷這條邊的兩個點是不是在一個聯通塊裡，如果在聯通兩個點的時候，還沒有合并就已經在一個集合就表示又環，不是樹，最後在判斷一下根節點有幾個，如果不止一個表示這是一個森林，而不是樹。

附上代碼，代碼在POJ上測試AC了，但在HDU上回WA，如果有哪位大佬發現了錯誤，還請大佬給本蒟蒻留言。

代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

int father[];

int get_father(int u)
{
    while(father[u]!=u)u = father[u];
    return u;
}

bool merge(int u,int v)
{
    if(get_father(u)==get_father(v))return false;
    father[get_father(u)] = get_father(v);return true;
}

void init()
{
    for(int i = ;i<;i++)father[i] = -;
}

int main()
{
    int u,v,num = ;
    while()
    {
        init();
        std::cin>>u>>v;
        if(u==&&v==){std::cout<<"Case "<<num++<<" is a tree."<<std::endl;continue;}
        if(u<||v<)return ;
        bool flag = false;
        while(!(u==&&v==))
        {
            if(father[u]==-)father[u] = u;
            if(father[v]==-)father[v] = v;
            if(merge(u,v)==false){std::cout<<"Case "<<num++<<" is not a tree."<<std::endl;flag = true;break;}
            std::cin>>u>>v;
        }
        if(flag==false)
        {
            int count = ;
            for(int i = ;i<;i++)
                if(father[i]==i)count++;
            if(count>){std::cout<<"Case "<<num++<<" is not a tree."<<std::endl;flag = true;}
        }
        if(flag==false)std::cout<<"Case "<<num++<<" is a tree."<<std::endl;
        else while(!(u==&&v==))std::cin>>u>>v;
    }
    return ;
}