W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mając dany graf nieskierowany, znajdź w nim cykl nieparzystej długości.
Wczytaj liczbę oznaczającą liczbę przypadków testowych oraz opisów grafów. Dla każdego z grafów należy stwierdzić, czy istnieje w nim cykl nieparzystej długości.
Pierwszy wiersz wejścia zawiera liczbę (). Dalej następuje opisów grafów nieskierowanych. Opis takiego grafu zawiera na początku dwie liczby i oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi (, ). Kolejne wierszy zawiera opis krawędzi. W każdym z tych wierszy znajdują się dwie liczby całkowite ze zbioru reprezentujące końce jednej krawędzi.
Dla każdego grafu z wejścia należy wypisać dokładnie jeden wiersz z odpowiedzią. Jeśli jest cykl, należy wypisać słowo TAK i po spacji kolejne wierzchołki cyklu. Wystarczy wypisać dowolny cykl, przy czym wierzchołki nie mogą się powtarzać. Jeśli cyklu nie ma, należy wypisać NIE.
Dla danych wejściowych:
2 4 6 1 2 1 3 1 4 2 3 2 4 3 4 4 4 1 2 2 3 3 4 4 1
poprawną odpowiedzią jest:
TAK 2 1 3 NIE
Autor zadania: Wojciech Śmietanka.