Witam serdecznie,
Ostatnio próbuję znaleźć sposób w jaki mógłbym rozwiązać następujące zadania:
Zadanie 1.
W grupie osób określamy relację A nie lubi B. Relacja ta nie jest symetryczna.
Jeżeli istnieje ciąg relacji A1 nie lubi A2, A2 nie lubi A3 ... Ak nie lubi A1,
to wszystkie osoby w takim cyklu przynależą do jednej grupy "nie lubienia".
Dla podanych na wejściu par określających relacje wyznacz podział na maksymalne
grupy "nie lubienia". Podaj złożoność i uzasadnij poprawność swojego rozwiązania.
Tutaj udało mi się rozwiązać zadanie za pomocą wyznaczania silnie spójnych składowych a dokładniej algorytmu Tarjana, aczkolwiek mam problem z wyznaczeniem złożoności.
Zadanie 2.
W grupie niegrzecznych dzieci istnieją pewne animozje. Przedszkolanka postanowiła
ustawić dzieci w rzędzie. Jeżeli A nie lubi B, to nie może stać w rzędzie przed B (aby nie rzucać w niego papierkami).
a) Określ, czy grupę dzieci można ustawić w jednym rzędzie
b) Jeżeli nie, to podaj minimalną liczbę rzędów koniczną do ustawienia dzieci.
c) Podaj minimalną liczbę rzędów konieczną do ustawienia dzieci, jeżeli:
Dziecko A nie lubi dziecka B, to musi stać w rzędzie o niższym numerze.
Podaj złożoność i uzasadnij poprawność swojego rozwiązania powyższych punktów.
Niestety nie mam za bardzo pomysłu jak rozwiązać zadanie 2. Czy ktoś z was spotkał się może z podobnym zadaniem i dałby parę wskazówek? :)
Z góry dziękuję za pomoc i pozdrawiam