Fişierul intrare/ieşire:g2mm.in, g2mm.outSursăSelectie echipe ACM ICPC, UPB 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

G2mm

Se da un graf conex si neorientat G, avand N noduri si M muchii. Distanta dintre doua noduri x si y ale unui graf G, distG(x,y) se defineste ca fiind numarul minim de muchii ce trebuie traversate pentru a ajunge de la un nod la celalalt. Patratul unui graf G (notat cu G2) se defineste in felul urmator:

  • are aceleasi noduri ca si graful G
  • are muchie intre doua noduri x si y, numai daca distG(x,y) ≤ 2 (distanta dintre nodurile x si y este cel mult 2, in graful G)

Determinati, daca exista, un cuplaj perfect in G2. Un cuplaj perfect intr-un graf H consta din N/2 muchii, astfel incat fiecare din cele N noduri ale lui H apare ca unul din cele 2 capete ale exact unei singure muchii din cadrul cuplajului.

Date de intrare

Prima linie a fisierului de intrare g2mm.in contine numerele intregi N si M, separate printr-un spatiu. Urmatoarele M linii contin cate 2 numere intregi x si y, separate printr-un spatiu, reprezentand doua noduri din graf care sunt conectate printr-o muchie. Nodurile grafului sunt numerotate de la 1 la N.

Date de iesire

Prima linie a fisierului de iesire g2mm.out va contine numarul intreg A, avand valoarea 1, daca exista un cuplaj perfect in patratul grafului dat, sau 0, in caz contrar. Daca A=1, atunci urmatoarele N/2 linii vor contine cate 2 numere intregi x si y, descriind cate o muchie a cuplajului perfect gasit.

Restrictii

  • 1 ≤ N ≤ 30.000, N par
  • N-1 ≤ M ≤ 200.000

Exemplu

g2mm.ing2mm.out
8 11
1 3
2 3
3 5
5 4
4 8
8 6
6 1
7 8
7 6
3 7
5 6
1
5 4
6 8
2 7
1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content