Pagini recente » Atasamentele paginii Profil ViiRalL | Statistici Megherlich Andreea (meghe) | Istoria paginii utilizator/sorin800 | Istoria paginii utilizator/cococozminz | clica

Mai intai trebuie sa te autentifici.

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-03-18 15:42:36.
Revizia anterioară Revizia următoare

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 $G=(V,E)$ se consideră următoarea operaţie. Mai întâi se construieşte graful orientat $G^\star=(V,E^\star)$ , având aceeaşi mulţime de vârfuri $V$ iar ca arce există un arc orientat $(u,v) \in E^\star$ dacă şi numai dacă în graful iniţial $G=(V,E)$ există un drum orientat de la vârful $u$ la vârful $v$ . Graful $G^\star=(V,E^\star)$ se numeşte închiderea tranzitivă a grafului $G=(V,E)$ .

Se defineşte o clică într-un graf orientat ca fiind o submulţime de vârfuri $U$ a mulţimii $V$ , asfel ca între oricare două vârfuri $u$ şi $v$ ale lui $U$ există un arc orientat fie de la $u$ la $v$ , fie invers de la $v$ la $u$ (sau ambele). Dimensiunea unei clici $U$ este numărul de vârfuri ale clicii.

O clică $U$ în $G^\star=(V,E^\star)$ corespunde unui subgraf $U$ în $G=(V,E)$ unde pentru oricare două vârfuri $u$ şi $v$ ale lui $U$ există în $G=(V,E)$ fie un drum orientat de la $u$ la $v$ , fie un drum orientat de la $v$ la $u$ , fie ambele.

Fiind dat un graf $G=(V,E)$ scrieţi un program care să calculeze dimensiunea maximă a unei clici $U$ a închiderii tranzitive $G^\star=(V,E^\star)$ 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 $N$ şi $M$ separate printr-un spaţiu, respectiv numărul de vârfuri şi de arce orientate ale grafului $G$ . Următoarea linie conţine $2M$ 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 $N$ ). 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.