Page 122 - MATINF Nr. 7

˘
122 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Date de ies , ire

Fis , ierul de ies , ire cc.out va cont , ine pe prima linie num˘arul de componente conexe ale grafului
din enunt , .

Exemplu

cc.in cc.out Explicat , ie
abaadghddgh 2 Nodurile grafului vor fi etichetate cu literele
a, b, d, g, h aflate ˆın alfabet pe pozit , iile 1, 2, 4, 7, 8.
Muchiile grafului sunt: [a, b], [a, d] s , i [d, g].
Graful are dou˘a componente conexe.

Costel B˘alc˘au, Pites , ti

I 103 (subgrafuri). Se d˘a un graf neorientat cu n noduri s , i m muchii. Pentru acest graf se
dores , te determinarea subgrafurilor complete cu num˘ar maxim de noduri. Aceste subgrafuri se
numesc clici.
Cerint , ˘a

Cunoscˆand n, m s , i cele m muchii se cere s˘a se determine num˘arul de subgrafuri cu proprietatea
din enunt , .

Restrict , ii

• 1 ≤ n ≤ 100.

Date de intrare

Fis , ierul subgrafuri.in cont , ine pe prima linie n s , i m separate printr-un spat , iu, apoi pe
urm˘atoarele m linii nodurile muchiilor separate prin cˆate un spat , iu.
Date de ies , ire

Fis , ierul de ies , ire subgrafuri.out va cont , ine pe prima linie num˘arul cerut ˆın enunt , .

Exemplu

subgrafuri.in sugrafuri.out Explicat , ie
9 10 3 Graful cont , ine 3 subgrafuri cu proprietatea
6 3 din enunt. Acestea au nodurile:
9 4 1 5 6
3 7 2 3 7
1 6 4 8 9
8 4
2 7
1 5
8 9
2 3
5 6

Doru Anastasiu Popescu, Pites , ti