天天看點

soj 1034 Forest_求樹的深度和寬度

題意:給你n個節點,m條邊,每條邊是有向的,這顆樹不能有自環,問這顆樹的深度和寬度

思路:

不合法情況

1,入度大于1,即存在兩條指向同一頂點的邊

2,一條入點和出點都相同的邊

3,一條變得入點和出點深度已知,但不符合出點的深度是入點的深度加1

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

5,周遊完以後,有頂點未周遊,說明有多個根

樹的寬度是指,同一層最多有多少個節點