is the generalized Bregman’s bound and the matrix scaling method.

The MCMC algorithm presented for random digraphs in [@FS92] can be naturally extended to dense digraphs. This algorithm is based on sampling 1-factors of the digraphs and uses the self-reducing method[@JVV86] to approximate the counting. Recently Bezáková et. al. present an algorithm that approximates the number of 1-factors in $O(n^7(\log n)^4)$ expected time, via an accelerating simulated annealing technique[@BSVV06].

The ratio of the number of 1-factors to the number of Hamiltonian cycles is established to be $O(n^{1+1/(2\alpha-3/2)})$ in this paper provided that the digraph is $\alpha n$ dense. Due to this ratio and Bezáková’s results in [@BSVV06], MCMC method[@FS92] runs in an $O(n^{13}(\log n)^4)$ time when $\alpha\geq.85$. Moreover, counting the number of Hamiltonian cycles in such digraphs is shown to be still $\#$P-Complete.

Our algorithm for counting Hamiltonian cycles is built on the acceptance/rejection algorithm in [@HL08] while a different sequential sampling procedure is constructed to ensure that the approximating target is the number of Hamiltonian cycles.

One of the remarkable advantages of acceptance/rejection method is that it samples perfectly from a given set, which removes the sampling error when the MCMC method is adopted. Hence, our algorithm generates a 