Solving a in/equality constraint problem with graph search
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.