如何使用搜索深度的递归代码找到图的最大深度？

Question

我用迭代方法解决了这个问题，但是很难应用递归方法来找到图的最大深度。这是 codeforces 问题 https://codeforces.com/problemset/problem/115/A 我猜它需要图形的最大深度作为解决方案。怎么解决啊

Answer 1

根据问题你得到一棵或多棵（并不是说只有一名员工得到-1）树。

不过我觉得问题很简单。正如您发现树的最大深度应该是组数。

所以在将输入解析为数组后，解决方案就是：

int employees[n];
int maxdepth = 0
for (int i = 0; i<n; ++i){
  int thisDepth = 0;
  int t = i;
  while(employees[t] != -1)
    t  = employees[t];
    thisDepth++;
  }
  if(thisDepth > maxDepth){
    maxDepth = thisDepth;
  }
}

递归方法如下所示：

int getDepth(const int i_employeeArray[], int i_employee){
   if( i_employeeArray[i_employee] == -1 ){
     return 0;
   } else {
     return 1+ getDepth(i_employeeArray, i_employeeArray[i_employee]);
   }
}


int employees[n];
int maxdepth = 0
for (int i = 0; i<n; ++i){
  int thisDepth = getDepth(employees, i);
  if(thisDepth > maxDepth){
    maxDepth = thisDepth;
  }
}

两者都可以通过存储已访问字段的计算深度来优化，但对于这个相当小的（<=2000 名员工）问题应该不是必需的。

如何使用搜索深度的递归代码找到图的最大深度？

How can I find the max depth of a graph with recursive code of depth of search?

algorithm

tree

graph

depth-first-search