I have the following question:

Split a set of n elements into 2 sets based on k conditions. Each of these conditions are in the form of "Z wants to be in the same set as X" and "Z does not want to be the in the same as Y" where Z != X and Z != Y. Find the elements in the two groups or state if it is not possible.

The first obvious method is to brute force every possible configuration in $$$O(k \cdot 2^n)$$$

The next would be to use some kind of graph structure in $$$O(n + k)$$$ time. With the first condition I was thinking about creating a DAG and then running topological sort on it, but I'm not sure how exactly that would work.

Anyone have any ideas?