Aparellament màxim P59669

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.