Zadanie w systemie SPOJ (main)
6631. Za rączki dzieci, za rączki
Kod zadania: ASD10PD


Twoja siostra, przedszkolanka, ma problem. Chciałaby pójść na spacer z dziećmi z przedszkola, ale trzeba je tak poustawiać dwójkami, aby w parze szły dzieci, które się lubią. W przedszkolu każda dwójka dzieci albo jednocześnie się lubi, albo się nie lubi. W parze nie mogą iść dzieci, które się nie lubią, bo będą rozrabiały na spacerze (tego nie chcemy).

Pomóż siostrze i sparuj jak najwięcej dzieci, te które nie da się sparować zostają w przedszkolu (wiem niedydaktyczne - część dzieci idzie, a część nie - dobrze, że nie jestem przedszkolankiem).

Pomóż także stwierdzić, czy można podzielić dzieci na dwie grupy tak, że w każdej podgrupie nie ma dwójki lubiących się dzieci.

Wejście
Na wejściu pojawi się najpierw n - liczba dzieci w przedszkolu (mniejsza od 50000 - ogromne przedszkole), następnie dodatnia liczba relacji 'lubienia' m (mniejsza od 1000000). Dalej w osobnych liniach pary dzieci, które się lubią:
a1 b1 [dzieci liczymy od 1, a nie jak informatycy od 0]
.....
am bm

Wyjście
Należy wypisać T lub N w zależności od tego czy znajdziemy dwie grupy dzieci o podanej charakterystyce; dalej po spacji maksymalną liczbą par, które siostra może wziąźć na spacer (może być 0) posortowana seria liczb przedzielonych spacjami mówiąca o tym jakie pary dzieci bierzemy na spacer. np 1 oznacza, że dziecko a1 i dziecko b1 idą na spacer w parze.

Przykład
Wejście:331 22 33 1Wyjście:N 1 1 [równie dobrze odpowiedzią może być 2 albo 3]Wejście:451 22 42 33 14 2 [powtórzenia (to samo co 2 4) mogą się zdarzyć]Wyjście:N 2 2 4 [inną prawidłową odpowiedzią jest 4 5]Wejście:651 23 23 44 16 5Wyjście:T 3 2 4 5 [inna prawidłowa odpowiedz to 1 3 5]
Uwagi do zadania:
Jak łatwo zauważyć będziemy mieli graf w którym należy znaleźć maksymalne skojarzenie (matching). Podział na grupy wg. opisu to pytanie, czy graf jest dwudzielny. Dla grafów dwudzielnych istnieją stosunkowo proste algorytmy znajdujące największe skojarzenie w grafie (algorytm Hopcrofta-Karpa). Skojarzenie w grafach ogólnych można znaleźć przy pomocy algorytmu Edmondsa.

Testy zostaną zaliczone jeśli poprawnie zostanie sprawdzona dwudzielność wszystkich grafów. Jeśli nie będzie znajdowane skojarzenie w grafie (np. jest zaimplementowane jedynie znajdowanie skojarzenia w grafach dwudzielnych), to wpisujemy 0 w informacji ile dzieci może iść na spacer.

Bibliografia:
- nieśmiertelny Cormen "Wstęp do algorytmów"
- artykuły Aleksandra Schrijvera; w szczególności A Course in Combinatorial Optimization

PS. Na wejściu może się pojawić wielokrotna krawędź!


--------------------------------------------------------------------------------
Dodane przez: Andrzej Jastrzębski
Data dodania: 2010-05-10
Limit czasu wykonania programu: 1s
Limit długości kodu źródłowego 50000B
Języki programowania: C C99 strict C++ 4.0.0-8 C++ 4.3.2