Programowanie c++

Drzewo - wyznaczenie wielkości poddrzewa

Kategoria: Informatyka - strona ogólna kategorii / programowanie c++
Drzewo - wyznaczenie wielkości poddrzewa - wersja bez DFS
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4.  
  5. stack <int> W;
  6. int LO[50];             //lista ojcow
  7. int IS[50];             //ilosc synow
  8. int WPD[50];    //wielkosc poddrzewa
  9.  
  10. void PDD (int);
  11.  
  12. int main()
  13. {
  14.         int n;
  15.         cin>>n;                 //ilosc wierzcholkow
  16.         /* wczytanie listy ojcow BEGIN */
  17.         for ( int i=1 ; i<=n ; i++ )
  18.                 cin>>LO[i];
  19.                
  20.         /* zliczanie ilosci synow BEGIN */     
  21.         for ( int i=1 ; i<=n ; i++ )
  22.                 IS[LO[i]]++;
  23.        
  24.         /* umieszczamy liscie na stosie BEGIN */                       
  25.         for ( int i=1 ; i<=n ; i++ )
  26.                 if (IS[i]==0)
  27.                         W.push(i);
  28.        
  29.         /* Dla wierzcholkow lezacych na stosie wywolujemy funkcje */   
  30.         while (!W.empty())
  31.                 PDD(W.top());
  32.                
  33.         /* wypisujemy wielkosc poszczeg poddrzew */
  34.         for ( int i=1 ; i<=n ; i++ )
  35.                 cout<<WPD[i]<<" ";                                     
  36. }
  37.  
  38. void PDD (int x)
  39. {
  40.         W.pop();
  41.         IS[LO[x]]--;
  42.         WPD[x]+=1;
  43.         WPD[LO[x]]+=WPD[x];
  44.         if (IS[LO[x]]==0)
  45.                 W.push(LO[x]);
  46. }