ACM程序设计题，高手答复

我就晕死了，没考虑到这种情况。

2

1 2 1 2

不是棵树。

害我挂了4次~~

我主要思想是：

根据输入建立一个关系链接矩阵。 然后找到无入度的点作为根点，开始深搜遍历，遍历过程中记录遍历过的点，当遍历过程中，如又碰到已经遍历的点，那么说明它肯定不是棵数。。。,因为此时已经存在了不止一条路径从根节点到该节点。

如果上判断通过，就判断是否所有的点被访问到了。。 如果 有，说明他可能是一个森林，至少不是树了。。。

我的 代码如下：

#include <stdio.h>

#include <memory>

#define MAX 50

bool relation[MAX][MAX]

int node_num

bool pass[MAX]

int flage

int index(int num)

{

static int index[MAX]

int i

for( i =0 i <node_num i ++ )

if(num == index[i]) return i

index[i] = num

node_num++

return i

}

int find_root()

{

int i , j

for( j =0 j <node_num j ++ )

{

for( i = 0 i <node_num i ++ )

if( relation[i][j] != 0 ) break

if(i >= node_num ) return j

}

return -1

}

void dfs( int node )

{

int i

for(i = 0 i <node_num i ++ )

if( flage == 0 &&relation[node][i] == true )

{

if(pass[i] == true) { flage = 1 return }

pass[i] = true

relation[node][i] = 0

dfs( i )

}

}

bool check_tree()

{

int root , i

if( ( root = find_root() ) <0 ) return false

pass[root] = true

dfs(root)

if(flage == 1 ) return false

for(i =0 i <node_num i ++ )

if(pass[i] == false) return false

return true

}

int main()

{

int cases, i , j , n , begin ,end

scanf("%d",&cases)

for(j = 0 j <cases j ++ )

{

memset(relation , false , sizeof(relation))

memset(pass,false,sizeof(pass))

node_num = 0

flage = 0

scanf("%d",&n)

for(i = 0 i <n i ++ )

{

scanf("%d %d",&begin,&end)

begin = index(begin)

end = index(end)

if(relation[begin][end] == true )

flage = 1

else relation[begin][end] = true

}

if(check_tree() == true) printf("Case %d is a tree.",j+1)

else printf("Case %d is not a tree.",j+1)

printf("\n")

}

return 0

}

首先要打好基础，掌握基本的数据结构和算法知识，精通一门语言的代码规范。

有了基础，最重要的就是多实践了，只有在实践中你才知道如何将知识运用在具体的程序设计中。碰到问题要多思考，靠自己解决问题，实在想不出来再求助他人。

世上无难事只怕有心人，相信自己！！！

---