I would like to merge connected nodes with a specific attribute of a directed acyclic graph. After each merge operation, the graph should remain acyclic. Let’s say my graph contains blue nodes and white nodes.

A and B are connected, they may be merged:

The above graph is DAG. **Merging node {A,B} with node {D} is illegal since it creates a cycle!**

My current algorithm is based on union-find.

`For each blue node b: Make-Set(b) merge blue nodes if they are connected `

The bug is the output graph contains cycles. How can I avoid merges that create cycles in the graph?