Șiret - IXIA

Șiret

== include(page="template/taskheader" task_id="siret") ==

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:

== include(page="template/ixia-winner" round_id="7" user_id="spatarel") ==

* Graful are exact atâtea noduri câte şireturi există.

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 faţă de altele. Şireturile sunt numerotate de la $1$ la $N$ in ordinea capetelor superioare. Având o astfel de configuraţie în faţă, Dani desenează din reflex un graf după următoarele reguli:
 
* Graful are $N$ noduri.

* 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.

Numim acest tip de graf un graf şiret. 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ă?
h2. Date de intrare

h3. Explicaţie

...

Configuratia de sireturi pe baza careia s-a construit graful din exemplu este urmatoarea.
!problema/siret?imag3.png!

== include(page="template/taskfooter" task_id="siret") ==
 

== include(page="template/taskfooter" task_id="siret") ==

8371