We consider the problem of determining whether a directed graph contai
ns a pair of vertices connected by two distinct simple paths. A straig
htforward implementation using n depth-first searches requires O(nm) t
ime on an n-vertex, m-arc digraph; we obtain an O(n2)-time algorithm b
y using contraction wherever possible.