Solving a in/equality constraint problem with graph search You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.


An equality constraint of the form xi = xj for some i!=j.
An inequality constraint of the form xi!= xj for some i!=j.


I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours. 

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?
You're on the right track.  Construct an undirected graph with an edge for each equality constraint, as you suggested.  Next, look into the concept of connected components, and algorithms for finding them.  You should be able to take it from here.

This problem can be solved in linear time.