Compute SCCs of the implication graph using Tarjan's or Kosaraju's algorithm. For each topping i, check if x_i and NOT x_i are in the same SCC. If yes for any topping: impossible to satisfy all customers. Print IMPOSSIBLE and exit immediately.
No assignment can work because you would need a topping both on and off. If no for all toppings: you can find a valid assignment. The graph structure allows it. Proceed to the construction phase where you build the actual solution.