| Fişierul intrare/ieşire: | neconex.in, neconex.out | Sursă | Lot Sibiu 2011 |
| Autor | Cosmin-Mihai Tutunaru, Pit-Rada Vasile | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.425 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Neconex
Pe internet circulă de ceva timp un joc nou numit "Neconex" care poate fi jucat de două persoane folosind un graf care nu este conex. Cei doi jucători mută alternativ. Printr-o mutare se înţelege adăugarea unei muchii între două noduri distincte între care nu există deja muchie. Pierde jucătorul la care se realizează conexitatea, adică toate nodurile grafului aparţin aceleiaşi componente conexe.
În loc să se pregătească pentru “Lotul Naţional de Informatică”, Ţirbi şi Birţi joacă acest joc, iar Ţirbi mută mereu primul. Deoarece ambii sunt destul de buni la algoritmică, ei joacă optim.
Date de intrare
Fişierul de intrare neconex.in conţine pe prima linie numărul T, iar pe următoarele linii va fi descris fiecare graf în parte. Descrierea fiecărui graf începe cu o linie ce conţine N şi M (reprezentând numărul de noduri şi numărul de muchii ale grafului), iar pe următoarele M linii se află câte două numere naturale A şi B reprezentând faptul că există o muchie între nodurile A şi B.
Date de ieşire
Fişierul de ieşire neconex.out conţine T linii, câte una pentru fiecare graf din fişierul de intrare. Pe linia i se va afla 1 dacă Ţirbi are strategie de câştig şi 0 în caz contrar.
Restricţii
- 1 ≤ T ≤ 31
- 2 ≤ N ≤ 20 000
- 0 ≤ M ≤ 20 000
- Se garantează că niciun graf din fişierul de intrare nu este conex.
- Prin joc optim se înţelege faptul că ambii jucători vor încerca să câştige.
- Pentru 15% din teste M = 0.
- Pentru 30% din teste T ≤ 13 şi N ≤ 20.
- Pentru 60% din teste N ≤ 1 000.
Exemplu
| neconex.in | neconex.out |
|---|---|
| 3 4 1 1 2 5 2 2 1 4 5 7 0 | 1 0 1 |
