Witam
Mam do zrobienia takie zadanko i nie mam najmniejszego pojecia jak sie za nie zabrac. Wiem tylko ze jest to algorytm oparty na grafie i sprawdzajacy czy spelniona jest formula 2-cnf. Z gory dzieki za kazda, nawet najmniejsza pomoc
Grupa podróżnych ma możliwość odwiedzenia kilku miast. Każdy podróżnik może podać dwa życzenia, do którego z miast chciałby lub nie chciałby się udać. Jedno życzenie wyraża chęć lub niechęć odwiedzenia dokładnie jednego miasta. Możliwe jest, że oba życzenia jednego wycieczkowicza są takie same lub tez, że są one przeciwne. Na przykład "chcę odwiedzić miasto A" i "nie chcę odwiedzić miasta A". Twoim zadaniem jest napisanie programu, który
czyta życzenia podróżników z pliku tekstowego,
sprawdza, czy jest możliwe utworzenie takiej listy miast do odwiedzenia (lista może być pusta), w której co najmniej jedno życzenie każdego podróżnika jest uwzględnione,
zapisuje listę miast do odwiedzenia do wyjściowego pliku tekstowego.
Wejście
Pierwsza linia pliku wejściowego zawiera dwie dodatnie liczby całkowite n i m (1<=n<=20000,1<=m<=8000); n jest liczbą podróżnych a m liczbą miast. Podróżni są numerowani od 1 do n a miasta od 1 do m. Kolejnych n linii zawiera dwie dodatnie liczby całkowite oddzielone pojedynczą spacją. i+1 -sza linia zawiera liczby wi1 oraz wi2 reprezentujące życzenia i-tego podróżnika -m<=wi1,wi2<=m, wi1, wi2<>0. Liczba dodatnia oznacza, że podróżny wyraża chęć odwiedzenia danego miasta, a ujemna, że podróżny nie chce odwiedzić danego miasta.
Wyjście
Twój program powinien wypisać w pierwszej linii pliku jedną nieujemną liczbę t oznaczającą ilość miast do odwiedzenia. W drugiej linii pliku powinno się znaleźć dokładnie t liczb całkowitych w rosnącym porządku reprezentujących miasta do odwiedzenia.
Przykład
Dla danych wejściowych:
3 4
1 -2
2 4
3 1
Prawidłowe wyjście wygląda następująco:
4
1 2 3 4