Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | siret.in, siret.out | Sursă | Infoarena Monthly 2012, Runda 7 |
| Autor | Vlad Duta | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Șiret
 Aceasta problema este sponsorizata de IXIA! Participantul inscris care va obtine cel mai mare punctaj va primi un premiu din partea sponsorului nostru. |
Obişnuit cu probleme ştiinţifice şi concepte abstracte, Dani a ajuns la o vârstă care îi solicită subtil să înveţe şi alte lucruri de natură mai prozaică. De exemplu să-şi lege şireturile. În viziunea lui Dani, şireturile sale sunt amplasate pe două axe paralele, iar fiecare şiret este un simplu segment care are un capăt pe o axă, iar celălalt capăt pe axa opusă. Se poate presupune că pe ambele axe capetele sunt situate echidistant unele fata de altele. Având o astfel de configuraţie faţă, Dani desenează din reflex un graf după următoarele reguli:
- Graful are exact atâtea noduri câte şireturi există.
- Există muchie neorientată de la nodul i la nodul j dacă şiretul i se intersectează cu şiretul j.
Numim acest tip de graf un graf şiret. Sau un graf viclean, depinzând de umorul fiecăruia. Numim clică a unui graf un subgraf al său care are muchie între oricare două noduri ale subgrafului.
Primind un graf şiret ca input, puteţi găsi clica sa de dimensiune maximă?
Date de intrare
Pe prima linie a fişierului siret.in se vor afla două numere N şi M, semnificând numărul de noduri respectiv numărul de muchii ale grafului.
Următoarele M linii vor conţine câte o pereche X Y cu semnificaţia că există muchie intre X şi Y.
Date de ieşire
Pe prima linie a fişierului siret.out se va afla un număr natural R, dimensiunea maximă a unei clici prezente în graful dat.
Pe cea de a doua linie se vor afla R numere reprezentând nodurile componente ale clicii găsite. Dacă există mai multe soluţii, se poate afişa oricare.
Restricţii
- 1 ≤ N ≤ 300
- 0 ≤ M ≤ N * (N - 1) / 2
- Se garantează ca graful dat este şiret. A reuşit să fure un tricou şi două perechi de papuci din vestiarul lui Real Madrid.
Exemplu
| siret.in | siret.out |
|---|---|
| 3 2 1 2 1 3 | 2 1 3 |
Explicaţie
...
