Fişierul intrare/ieşire: | clica.in, clica.out | Sursă | utcn-2021 |
Autor | Tudor Muresan | Adăugată de | Ciprian Oprisa •cypry |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Clică de dimensiune maximă
Fiind dat un graf orientat se consideră următoarea operaţie. Mai întâi se construieşte graful orientat , având aceeaşi mulţime de vârfuri iar ca arce există un arc orientat dacă şi numai dacă în graful iniţial există un drum orientat de la vârful la vârful . Graful se numeşte închiderea tranzitivă a grafului .
Se defineşte o clică într-un graf orientat ca fiind o submulţime de vârfuri a mulţimii , asfel ca între oricare două vârfuri şi ale lui există un arc orientat fie de la la , fie invers de la la (sau ambele). Dimensiunea unei clici este numărul de vârfuri ale clicii.
O clică în corespunde unui subgraf în unde pentru oricare două vârfuri şi ale lui există în fie un drum orientat de la la , fie un drum orientat de la la , fie ambele.
Fiind dat un graf scrieţi un program care să calculeze dimensiunea maximă a unei clici a închiderii tranzitive a grafului dat.
Date de intrare
Fişierul de intrare clica.in conţine mai multe teste. Prima linie a testului conţine două numere întregi şi separate printr-un spaţiu, respectiv numărul de vârfuri şi de arce orientate ale grafului . Următoarea linie conţine numere întregi separate de spaţiu, fiecare pereche de numere consecutive reprezentând un arc al grafului (vârfurile sunt numere de la 1 la ). Este garantat că fiecare arc apare o singură data şi nu există bucle (adică extremităţile fiecărui arc sunt distincte). Fişierul se termină cu numărul 0.
Date de ieşire
Pentru fiecare exemplu de test, în fişierul clica.out se tipăreşte numărul exemplului (începând cu 1) urmat de ':' şi de dimensiunea maximă a unei clici a închiderii tranzitive a grafului dat.
Restricţii
Exemplu
clica.in | clica.out |
---|---|
4 4 1 2 2 3 3 4 4 1 0 | 1:4 |
Explicaţie
Graful din exemplu are 4 vârfuri şi 4 arce: (1, 2), (2, 3), (3, 4) şi (4, 1). Deoarece graful este un ciclu, există un drum orientat între oricare două vârfuri, deci clica maximă conţine toate nodurile grafului.