判断是否为树 - Is It A Tree?

这个题目,是使用数学方法来解答的

Posted by isheng on July 17, 2016

判断是否为树利用数学关系答题


原题题目

A - Is It A Tree?

Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u

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.


我的思路

当初看到这个题目得时候,还是被惊呆了,除了能看懂标题外,其他的不知道到底在讲什么,用了翻译工具也是看的云里雾里的,不过幸好的是有大神帮我翻译了这道题目,就是一个判断一个图是否为树的题目,幸好哥们我离散数学刚考完没忘记,在离散数学中树的节点数 = 边数 + 1,有了这个关系,我就放心的coding代码了!

调试过程

在第一次提交的时候发现超时了,可是根据我的程序,数组只有10个这么大,超时是不应该的,交流了一下,应该是边界条件的判断除了问题,我设置的树最多只有9个节点,都是从1-9这九个数字中选择的,可是通过仔细翻译这个题目发现,它给的提示是整数,所以赶紧修正了这个问题。

问题代码
int Week2TextA[10],WeekText5[10];
//建节点统计表。
修正后的代码
#define w2max 20000

int Week2TextA[w2max],WeekText5[w2max];//建节点统计表。

设置了一个两万的数组,果然通过了题目,成功AC了。

感想与改进

这道题是英文题,蛮简单的,但是要学会翻译才行,改进正在看别人的代码中,正在寻找一个内存开销小的代码来节省内存,时间复杂度为n。

AC代码

#include <cstdio>
#include <iostream>
using namespace std;
#define w2max 20000

int Week2TextA[w2max],WeekText5[w2max];//建节点统计表。

void w2ta_star(){
    for (int i = 0; i < w2max; ++i) {//初始化数据
        Week2TextA[i] = 0;
        WeekText5[i] = 0;
    }
}

int main(){
    int a,b,num,map,n = 0;
//    freopen("in.txt", "r", stdin);
    while(1){
        n ++;
        num = 0,map = 0;
        int ok = 0;
        w2ta_star();
        while(scanf("%d %d",&a,&b)){
            if(a == 0 || b == 0) break;
            if(a == -1 || b == -1) break;
            Week2TextA[b] ++;//统计节点数量
            WeekText5[a] ++;//统计节点数量
            num ++;//统计边的数量
        }
        if(a == -1 || b == -1) break;
        for (int i = 1; i < w2max; ++i) {//处理的数量
            if(Week2TextA[i] > 1) {//判断是否每个节点只有一条有向边指向它
                ok = 0;
                break;
            }
            else if(WeekText5[i] > 0 || Week2TextA[i] > 0) map ++;
            else continue;
        }
        if(num == map - 1 ){//根据离散数学公式:边数 = 节点数 - 1 判断该图为树
            ok = 1;
        }
        if(num == 0) ok = 1;//排除空树特殊情况
        if(ok == 1) printf("Case %d is a tree.\n",n);
        else printf("Case %d is not a tree.\n",n);
        if(a == -1 || b == -1) break;//程序终止的条件
    }
    return 0;
}

加油,Coding是最有趣的事情!