Isomorfisme de grafs P65235

Donats dos grafs no dirigits G₁ i G₂ amb n vèrtexs i m arestes cadascun, podeu determinar si són isomorfs, és a dir, si són bàsicament el mateix graf?

Suposeu que els n vèrtexs es numeren començant en 0. Més formalment, cal determinar si existeix alguna bijecció f : { 0, …, n − 1 } → { 0, …, n − 1 } tal que, per a cada parell de vèrtexs (x, y), x i y estan connectats amb una aresta a G₁ si i només si f(x) i f(y) estan connectats amb una aresta a G₂.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides de les m arestes de G₁, seguides de les m arestes de G₂. Suposeu 2 ≤ n ≤ 14 i 0 < m < n(n − 1)/2. No hi ha més d’una aresta entre cada parell de vèrtexs, ni arestes entre un vèrtex i ell mateix.

Sortida

Per a cada cas, escriviu “yes” o “no” segons convingui.

Puntuació

La solució esperada és un backtracking raonablement optimitzat. El jutge us donarà una estimació de la nota màxima que podeu treure (7 o 10) en funció de l’eficiència del vostre codi. En qualsevol cas, tots els últims enviaments s’avaluaran manualment, inclosos els que rebin 0 punts automàtics.