We present an O(dn2 + m)-time algorithm for exploring (constructing) an unknown strongly connected graph G with m edges and n vertices by traversing at most dn2 + m edges. Here, d is the minimum number of edges needed to add to G to make it Eulerian. This parameter d was introduced by Deng and Papadimitriou and is known as the deficiency of a graph. Subsequently, Albers and Henzinger gave an algorithm that achieves an upper bound of O (d6d2 log dm) edge traversals. Our bound is an improvement over these earlier bounds.