Pagini recente » Atasamentele paginii Profil Norryna | Atasamentele paginii Profil Vally77 | Atasamentele paginii Profil teodor345 | Atasamentele paginii Profil AAlexandru | clica

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

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.

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 $G^\star$ a grafului dat.

Restricţii

$3 \leq N \leq 10^4$
$3 \leq M \leq 10^6$

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta