Как найти максимальную глубину графа с рекурсивным кодом глубины поиска?

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 сотрудников) проблемы. </p>