Sa consideram secvente de grafuri neorientate de tipurile urmatoare:

Tipul $A$

* Tipul $A$

Secventa grafurilor de tip $A$ se construieste in modul ce se poate deduce din exemplele urmatoare:

   $A1$ $A2$  $A3$      $A4$        $A5$
 
imagine
 
Observaţi că graful $An$ are $2n$ varfuri.
 
Tipul $B$

     $A1$        $A2$       $A3$            $A4$        $A5$
!problema/perfect?poza1.jpg!
Observati ca graful $An$ are $2n$ varfuri.
* Tipul $B$

Secventa grafurilor de tip $B$ se construieste dupa modelul urmator:

       $B1$  $B2$    $B3$      $B4$

     $B1$        $B2$       $B3$            $B4$
!problema/perfect?poza2.jpg!
* Tipul $C$
Secventa grafurilor de tip $C$ se construieste dupa modelul urmator:
     $C1$     $C2$         $C3$            $C4$
!problema/perfect?poza3.jpg!

imagine 2

Se numeste cuplaj perfect in graf o modalitate de a alege muchii ale grafului astfel incat oricare varf din graf sa fie incident cu exact o muchie aleasa. Doua cuplaje sunt distincte daca exista o muchie care apartine unui cuplaj, dar nu apartine celuilalt.

Tipul $C$
Secventa grafurilor de tip $C$ se construieste dupa modelul urmator:
  $C1$     $C2$         $C3$            $C4$

h2. Cerinta

imagine 3

Dat fiind un graf de unul dintre tipurile din enunt, sa se determine numarul de cuplaje perfecte distincte ale grafului respectiv.

Se numeste cuplaj perfect in graf o modalitate de a alege muchii ale grafului astfel incat oricare varf din graf sa fie incident cu exact o muchie aleasa. Două cuplaje sunt distincte daca exista o muchie care apartine unui cuplaj, dar nu apartine celuilalt.

h2. Date de intrare

Fisierul de intrare $perfect.in$ ...

Fisierul de intrare $perfect.in$ contine o singura linie pe care se afla un caracter si un numar natural nenul $n$, separate printr-un spatiu. Caracterul poate fi $A$, $B$ sau $C$ si indica tipul grafului. Numarul natural $n$ indica numarul de ordine al grafului in secventa de grafuri de tipul specificat de caracter.

h2. Date de iesire

In fisierul de iesire $perfect.out$ ...

Fisierul de iesire $perfect.out$ va contine o singura linie pe care va fi scris numarul de cuplaje perfecte ale grafului din fisierul de intrare.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 100$

h2. Exemplu
table(example). |_. perfect.in |_. perfect.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| A 4
| 5
|
| B 2
| 4
|
| C 2
| 8
|

h3. Explicatie

...

Cele $5$ cuplaje perfecte ale grafului $A4$ sunt:
 
!problema/perfect?exp1.jpg!
 
Cele $4$ cuplaje perfecte ale grafului $B2$ sunt:
 
!problema/perfect?exp2.jpg!
 
Cele $8$ cuplaje perfecte ale grafului $C2$ sunt:
 
!problema/perfect?exp3.jpg!

== include(page="template/taskfooter" task_id="perfect") ==

3135