Ilu Podwładnych?

Zadanie

W firmie każdy pracownik podlega kierownikowi prócz najwyższego kierownika (podlegającego sobie). Mając daną listę pracowników i ich kierowników określ ile każdy pracownik ma podwładnych. Zakładamy, że pracownicy mają przypisane id będące kolejnymi liczbami nieujemnymi.

Przykład

Przypuśćmy, że firma składa się z 7 osób i hierarchia pracowników przedstawia się następująco:

Hierarchia w firmie

Pomiędzy dwoma połączonymi pracownikami kierownikiem jest ten, który znajduje się wyżej na przedstawionym rysunku. Oznacza to, że (główny) kierownik 2 jest bezśporednim zwierzchnikiem 1, 3 oraz 4, ale właśsciwie podlegają mu wszyscy pracownicy (zgodnie z zadaniem nawet on sam). Do programu taka hierarchia zostałaby wprowadzona jako następujący zestaw danych:

1. 0 3
2. 1 2
3. 2 2
4. 3 2
5. 4 2
6. 5 1
7. 6 3

Na podstawie tych danych należy określić, że pracownik 3 jest kierownikiem dwóch pracowników, ale, że pracownik 2 jest kierownikiem, aż 6 osób!

Algorytm

Istnieje wiele sposobów na rozwiązywani tego typu zadań. Najprostszy z nich polega najpierw na pogrupowaniu informacji, którzy pracownicy komu podlegają. Na koniec tej operacji powinniśmy otrzymać listę o takiej długości ilu jest pracowników i po i-tą pozycją znajdą się wszyscy podlegli bezpośrednio kierownikowi i.

Następnie potrzebna jest pusta tablica o n pozycjach, gdzie n oznacza ilość pracowników. Na początku wybieramy kierownika głównego, którego można poznać po tym, że jego id pokrywa się z id kierownika. Następnie dla każdego z jego bezpośrednio wywołujemy sprawdzenie ile oni mają podwładnych. Warunkiem stopu jest sytuacja, gdy dany pracownik nie jest czyimś zwierzchnikiem. Wtedy taka osoba jest liczona jako 1 dla kierownika. Z kolei taka osoba ma wpisane 0, że nikt jej nie podlega. Po zakończeniu rekurencji w tablicy zapisane są informacje ile każdy z pracowników ma podwładnych.

Implementacja

Przechowywanie danych

Na początku deklarowany jest obiekt pracownik, który może przechowywać zarówno id pracownika jak również id jego kierownika. W celu uproszczenia wczytywania dodatkowo zostało napisana funkcja tworząca instancję pracownika z zadanami danymi.

1. struct pracownik {
2.   int id;
3.   int kierownik;
4. };
6. pracownik utworzPracownika(int id, int kierownik) {
7.   pracownik p;
8.   p.id = id;
9.   p.kierownik = kierownik;
10.   return p;
11. }

Liczenie Podwładnych

Funkcja szukajPodwladnych() przeprowadza najpierw grupowanie osób. Podczas grupowania zostaje znaleziony kierownik i jego id zostaje przechowane jako punkt startowy do dalszych obliczeń. Po przygotowaniu listy można policzyć ilu jest podwładnych.

1. int* szukajPodwladnych(pracownik* pracownicy, int n) {
2.   vector< vector<int> > lista(n);
3.   int glowny = -1;
4.   for (int i = 0; i < n; i++) {
5.     if (pracownicy[i].id == pracownicy[i].kierownik) {
6.       glowny = i;
7.     } else {
8.       lista[pracownicy[i].kierownik].push_back(i);
9.     }
10.   }
11.   int* dane = new int[n];
12.   dane[glowny] = policzPodwladnych(lista, dane, glowny);
13.   return dane;
14. }

Liczenie podwładnych przeprowadz funkcja policzPodwladnych(), która rekurencyjnie wyznacza ile osób ma podwładnych ma każda kolejna osoba. W każdym wywołaniu funkcja oblicza sumę podwładnych każdej osoby, której jest bezpośrednim kierownikiem. Oczywiście należy pamiętać, że każda osoba podwładna liczy się do sumy jako jej liczba podwładnych powiększona o 1 (o nią samą).

1. int policzPodwladnych(vector< vector<int> > &lista, int* dane, int teraz) {
2.   int suma = 0;
3.   for (int i = 0; i < lista[teraz].size(); i++)
4.     suma += policzPodwladnych(lista, dane, lista[teraz][i]) + 1;
5.   dane[teraz] = suma;
6.   return suma;
7. }

Testowanie funkcji

Przedstawiony fragment kodu wczytuje od użytkownika szukane informacje, a następnie wyświetla w rosnącym porządku id pracownika w pierwszej kolumnie, a w drugiej liczbę mu podległych.

1. int main () {
2.   int n, t1, t2;
3.   cout << "Ilu jest pracownikow?\n n = ";
4.   cin >> n;
5.   cout << "Podaj pracownikow i ich kierownikow:\n";
6.   pracownik* pracownicy = new pracownik[n];
7.   for (int i = 0; i < n; i++) {
8.     cin >> t1 >> t2;
9.     pracownicy[i] = utworzPracownika(t1, t2);
10.   }
11.   int* dane = szukajPodwladnych(pracownicy, n);
12.   for (int i = 0; i < n; i++)
13.     cout << i << "\t" << dane[i] << endl;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja