Risolvere un problema di vincolo in/uguaglianza con la ricerca del grafico

Question

Ti viene fornito un elenco di vincoli m su n variabili distinte x1, ..., xn. Ogni vincolo è di uno dei seguenti due tipi.

1. Un vincolo di uguaglianza della forma xi = xj per alcuni i! = J.
2. Un vincolo di disuguaglianza della forma xi! = Xj per alcuni i! = J.

Voglio trovare un incarico, se esiste, per ogni variabile in modo tale da essere conforme a tutti i vincoli che utilizzano un algoritmo di ricerca grafico nel tempo O (M+N).

Questo mi ricorda il problema della colorazione del grafico, tuttavia ciò comporta solo il controllo dei vicini del grafico in cui in qualsiasi grafico efficiente che potrei pensare, i nodi che condividono un vincolo potrebbero non essere vicini.

Il mio primo pensiero è stato quello di creare un grafico in modo tale che tutti i nodi uguali sono collegati, quindi usano DFS per attraversare ogni nodo e verificare se ha una disuguaglianza con un genitore, tuttavia non sembra molto efficiente come per ogni nodo (m) i Devo attraversare ogni vincolo di disuguaglianza (al massimo N) che mi porta al tempo NM, dove come DFS ha intrinsecamente O (M+N) su una rappresentazione ideale.

Qualche indizio?