Mój zwykły program działa wolno

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int root=0;
  int n;
  cin>>n;
  int ** info = new int *[n];
    for (int i = 0; i < n; i++)
    {
    	info[i] = new int [n];
    	info[i][n-1] = 0;
	}
  int a[n];
  queue<int>q;
  for(int i = 0 ; i < n; i++)
  {
	  cin >> a[i];
	  if(a[i] == -1)
	  {
	  	 root=i;
	  }
	  else {
	  	int j = info[a[i]][n-1];
	  	info[a[i]][j] = i;
		info[a[i]][n-1]++;   
	  }
  }
  int height=0;
  q.push(root);
  int k = 1;
  while(1)
  { 
	  int nodes=k;
	  if(nodes == 0)
	  {
		  cout << height << endl;
		  return 0;
	  }
	  height++;
	  k = 0;
	  while(nodes > 0)
	  {
		int node = q.front();
		q.pop();
		    if( info[node][n-1] > 0)  
		    {
			    for(int i = 0; i < info[node][n-1]; i++)
			    {
			  	 q.push(info[node][i]);
			     k++;
			    }
		    }
		nodes--;
	  }
  }
}

dlaczego powyższy kod działa co najmniej kilkadziesiąt razy wolniej niż poniższy kod?

#include <bits/stdc++.h>
using namespace std;
int root=0;
int main()
{
  int n;
  cin>>n;
  vector< vector<int> >nodes(n);
  queue<int>q;
  int a[n];
  for(int i=0;i<n;i++)
  {
	  cin>>a[i];
	  if(a[i]==-1)root=i;
	  else {
		  nodes[a[i]].push_back(i);
	  }
  }
  q.push(root);
  int height=0;
  while(true)
  {
	  int nodecount=q.size();
	  if(nodecount==0){
		  cout<<height<<endl;
		  return 0;
	  }
	  height+=1;
	  while(nodecount>0){
		  int node=q.front();
		  q.pop();
		  if(!nodes[node].empty()){
			  for(int i=0;i<nodes[node].size();i++)
				  q.push(nodes[node][i]);
		  }
		  nodecount--;
	  }
  }
    return 0;
}

Przykładowe poprawne wejście do obu programów to np.:

5
4 -1 4 1 1

lub

100
57 51 34 39 74 97 -1 22 71 22 18 97 59 67 74 38 89 50 25 7 81 77 10 86 83 13 44 28 15 7 41 92 47 39 49 7 56 72 80 17 78 15 61 58 45 28 65 39 91 90 97 82 71 81 40 79 8 77 54 82 8 93 54 65 57 83 52 71 58 95 57 44 31 33 34 41 98 11 66 72 93 12 64 68 3 60 59 26 9 88 6 59 97 74 22 24 31 29 70 18

Liczą one wysokość drzewa mając podanego na wejściu "rodzica każdego dziecka".
Czyli rozpiska dzieci każdego rodzica dla tego przykładu :

4 -1 4 1 1
0  1 2 3 4

wygląda tak

0: []
1:[3, 4]
2:[]
3:[]
4:[0, 2]