Consider the problem of finding connected components in a directed graph. Assume we have a node and we want to find all the nodes that are in the same connected component as the given node.

The first thought that comes to mind is: given a node X, find those
nodes Y that are reachable from X and from which you can get back to
X. So we will assume that edges are given by an `edge/2`

relation:

sameSCC(X,Y) :- reach(X,Z), reach(Z,Y). :- table reach/2. reach(X,X). reach(X,Y) :- reach(X,Z), edge(Z,Y).

Indeed given a node X, this will find all nodes in the same strongly
connected component as X, however it will in general take *O*(*n***e*)
time, where *n* is the number of nodes and *e* is the number of edges.
The reason is that given an X, there are *n* possible Z values and for
each of them, we will find everything reachable from them, and each
search can take *O*(*e*) time.

However, we can do better. It is known that this problem can be
solved in *O*(*e*) time. The idea is, given a node X, to find all nodes
reachable from X following edges forward. Then find all nodes
reachable from X following edges backward (i.e., follow edges against
the arrow.) Then intersect the two sets. That will be the set of
nodes in X's SCC, because if Y is in both these sets, you can follow
the edges forward from X to Y and then since there is also a backwards
path from X to Y, there is forward path from Y to X, so you can get
from X to Y and back to X following edges forward. So the program
that does this is:

% sameSCC(+X,-Y) sameSCC(X,Y) :- reachfor(X,Y), reachback(X,Y). :- table reachfor/2, reachback/2. reachfor(X,X). reachfor(X,Y) :- reachfor(X,Z),edge(Z,Y). reachback(X,X). reachback(X,Y) :- reachback(X,Z),edge(Y,Z).

Let's now consider its complexity to see why it is *O*(*e*). For a
fixed value X, the computation of the query `reachfor(X,Y)`

takes
*O*(*e*) time. Then we may have *O*(*n*) calls to `reachback(X,Y)`

(one for each Y) but they all use one underlying call to
`reachback(X,_)`

which takes *O*(*e*) and is done only once. So
when we add all that up (assuming a connected graph), we get *O*(*e*)
time.