Isomorfisme de grafs P65235

Donats dos grafs no dirigits $G_1$ i $G_2$ 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, \dots, n - 1 \} \to \{ 0, \dots, n - 1 \}$ tal que, per a cada parell de vèrtexs $(x, y)$, $x$ i $y$ estan connectats amb una aresta a $G_1$ si i només si $f(x)$ i $f(y)$ estan connectats amb una aresta a $G_2$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$, seguides de les $m$ arestes de $G_1$, seguides de les $m$ arestes de $G_2$. Suposeu $2 \le n \le 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.