Aparellament màxim P59669


Statement
 

pdf   zip

thehtml

Donat un graf no dirigit amb n vèrtexs, un aparellament és un subconjunt de les arestes sense cap vèrtex en comú. Feu un programa que digui si un graf donat té un aparellament màxim, és a dir, un agrupament dels vèrtexs en n/2 parells de manera que tots els vèrtexs estiguin en algun parell, i que els dos vèrtexs de cada parell estiguin connectats directament.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i el nombre d’arestes m, seguits de m parells de vèrtexs. Suposeu 2 ≤ n ≤ 20, que n és parell, que els vèrtexs es numeren de 1 a n, que no hi ha arestes repetides ni connectant un vèrtex amb ell mateix, i que no hi ha cap vèrtex de grau zero.

Sortida

Per a cada cas, digueu si el graf té algun aparellament màxim.

Observació

Hi ha algorismes polinòmics, més o menys complicats, per resoldre aquest problema. Aquí, ens conformem amb un simple backtracking.

Public test cases
  • Input

    2 1
    1 2
    
    4 4
    1 2
    3 1
    4 1
    2 3
    
    4 3
    1 2
    1 3
    1 4
    
    6 8
    1 2
    1 4
    2 3
    2 5
    2 6
    3 4
    4 5
    4 6
    

    Output

    si
    si
    no
    no
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++