Поиск количества узлов на каждом уровне во время bfs

Question

Вам дано Дерево, состоящее из N узлов. Дерево - это полностью связанный граф, состоящий из N узлов и краев N-1. Узлы в этом дереве индексируются от 1 до N. Рассмотрим узел, проиндексированный 1, как корневой узел этого дерева. Корневой узел лежит на уровне один в дереве. Вам дается дерево и целое число x. Вам нужно узнать количество узлов, лежащих на уровне x.

Входного формат

Первая строка состоит из одного целого числа N, обозначающее количество узлов в дереве. Каждая из следующих n-1 строк состоит из 2 целых чисел a и b, обозначающих неориентированный край между узлом a и узлом b. Следующая строка состоит из одного целого x.

Формат вывода

Вам нужно распечатать один целых чисел, обозначающих число узлов на уровне х.

---

Ниже приведен фрагмент кода, который я написал, и его неправильная информация. Пожалуйста, помогите мне найти ошибку.

import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.Scanner; 

public class LevelNodes { 
    public static ArrayList[] adj; 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int N = sc.nextInt(); 
     boolean[] visites = new boolean[N]; 
     ArrayList[] adj = new ArrayList[N]; 
     for(int j=0;j<N;j++){ 
      adj[j] = new ArrayList(); 
     } 
     for(int i = 0;i < (N-1) ;i++){ 
      int a = sc.nextInt(); 
      int b = sc.nextInt(); 
      adj[a-1].add(b); 
      adj[b-1].add(a); 
     } 
     int level = sc.nextInt(); 
     int counter = 0; 
     LinkedList list = new LinkedList(); 
     list.add(1); 
     counter++; 
     while(!list.isEmpty()){ 
      int n = (Integer) list.poll(); 
      for(int x = 0; x< adj[n-1].size();x++){ 
       list.add(adj[n-1].get(x)); 
      } 
      counter++; 
      if(counter == level){ 
       System.out.println(list.size()); 
       break; 
      } 

     } 
    } 

} 

Answer 1

Есть целый ряд проблем в коде:

Первая проблема заключается в том, что ваш код не может кончить. Это связано с тем, что вы добавляете оба края u-> v и v-> u в список смежности. Поэтому всякий раз, когда вы проводите опрос u из списка и добавляете его соседей, вы добавите v в список. Аналогично, всякий раз, когда вы проводите опрос v и добавляете его соседей, вы собираетесь добавить обратно u в список. Вам необходимо поддерживать логический массив visited и устанавливать visited[u]=true всякий раз, когда вы добавляете u в список. Таким образом вы можете добавить в список сканирования только невидимые узлы.

Еще одна серьезная проблема заключается в цикле while. Вы увеличиваете переменную счетчика уровня counter++; всякий раз, когда вы посещаете новый узел. Рассмотрим ниже дерево и предположим, что нам нужно найти количество узлов на уровне 2 (последний уровень).

 1 
    /\ 
    2 3 
/\/\ 
4 5 6 7 

Первоначально ваш список содержит 1 и counter=1. На первой итерации вы опросите 1 из списка и добавьте его соседей: 2 и 3. На этом этапе counter=2. В следующих двух итерациях вы собираетесь удалить 2 из 3 из списка, добавить своих соседей и прирастить counter каждый раз. Таким образом, к тому времени, когда вы достигнете второго уровня, counter будет равно 4. Оператор If никогда не будет выполнен.

Чтобы исправить это, вам необходимо увеличить counter, если вы закончили обработку всего узла на текущем уровне. Простой (непроверенный) способ сделать это - использовать второй временный список для хранения соседей всех узлов на текущем уровне. Затем, когда исходный список пуст, вы знаете, что обработали все узлы на текущем уровне. Здесь вы увеличиваете counter и перемещаете все узлы из временного списка в основной список.

while(!list.isEmpty()){ 
    int n = (Integer) list.poll(); 
    for(int x = 0; x< adj[n-1].size();x++){ 
     tmpList.add(adj[n-1].get(x)); 
    } 

    if(list.isEmpty()) { 
     if(counter == level){ 
      System.out.println(tmpList.size()); 
      break; 
     } 

     list.addAll(tmpList); 
     tmpList.clear(); 
     counter++; 
    } 
}