天天看点

soj 1034 Forest_求树的深度和宽度

题意:给你n个节点,m条边,每条边是有向的,这颗树不能有自环,问这颗树的深度和宽度

思路:

不合法情况

1,入度大于1,即存在两条指向同一顶点的边

2,一条入点和出点都相同的边

3,一条变得入点和出点深度已知,但不符合出点的深度是入点的深度加1

4,点入深度未知但出点深度已知

5,遍历完以后,有顶点未遍历,说明有多个根

树的宽度是指,同一层最多有多少个节点