Page 14 - MATINF Nr. 13-14

14 D.A. Popescu, C. B˘alc˘au, D. Constantin

Date de ies , ire
Pe prima linie a fis , ierului de ies , ire compeuler.out se va afis , a un singur num˘ar reprezentˆand
num˘arul maxim de noduri dintr-o component˘a conex˘a, cˆand cerint , a este C = 1, respectiv
num˘arul de componente conexe care sunt subgrafuri euleriene nevide, cˆand cerint , a este C = 2.

Restrict , ii s , i preciz˘ari
1. 1 ≤ N ≤ 1000.
2. 1 ≤ M ≤ 10000.
3. Pentru rezolvarea corect˘a a cerint , ei 1 se vor acorda 40 de puncte.
4. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 60 de puncte.

Exemplu

compeuler.in compeuler.out
1 3
6 4
1 4
5 2
3 2
3 5
2 1
6 4
1 4
5 2
3 2
3 5

Explicat , ii
Pentru cerint , a 1, exist˘a 3 componente conexe avˆand mult , imile de noduri: {1, 4}, {2, 3, 5},
a
{6}. Deci 3 este num˘arul maxim de noduri dintr-o component˘ conex˘a.
Pentru cerint , a 2, dintre cele 3 componente conexe doar a doua este subgraf eulerian nevid.
Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘ disponibil˘a: 64 MB.
a
Solut , ie

Cerint , a 1 ( 40 puncte)

a
Se determin˘ componentele conexe, folosind o modalitate de parcurgere a unui graf neorientat.
Cerint , a 2 ( 60 puncte)

Se utilizeaz˘a Teorema lui Euler de caracterizare a grafurilor euleriene.

Problema 2 - multigraf
Numim multigraf k-complet de ordinul n un graf cu n noduri, etichetate cu 1, 2, . . . , n, ˆın
care ˆıntre orice dou˘ noduri diferite exist˘a exact k muchii.
a
Cerint , e

Cunoscˆand n s , i k, se cere s˘a se determine num˘arul de arbori part , iali ai unui multigraf
k-complet de ordinul n.