We propose a version of DFS designed for Constraint Programming, called bimodal DFS, inspired by the partially-complemented graphs and that scales to both sparse and dense graphs.

Bimodal DFS is motivated by the elementary functions over integer variables which enable efficient iteration over the domain and efficient check for the presence of a value in the domain.

It runs in $O(n+\tilde{m})$ time, where $\tilde{m}$ is the sum, for each vertex $v$, of the minimum between the numbers of successors and non-successors of $v$.

Integrating it into Régin's GAC algorithm for the alldifferent constraint results in faster performance as the problem size increases.

In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.