Pagini recente » Istoria paginii utilizator/frumcrs | Diferente pentru utilizator/nightraven intre reviziile 4 si 3 | Istoria paginii utilizator/dariestefan | Statistici andy andy (andi_andrey14) | clica

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-03-18 15:17:58.
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

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.

Date de intrare

Fişierul de intrare clica.in ...

Date de ieşire

În fişierul de ieşire clica.out ...

Restricţii

... ≤ ... ≤ ...

Exemplu

clica.in	clica.out
This is some text written on multiple lines.	This is another text written on multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta