<p>There is a expected running time O(n^{3/2}) algorithm.</p>

<p>If you generate a uniform random digraph with m vertices such that each vertex has k labelled out-arcs (a k-out digraph), then with high probability the largest SCC (strongly connected component) in this digraph is of size around c_k m, where c_k is a constant depending on k. Actually, there is about 1/\sqrt{m} probability that the size of this SCC is exactly c_k m (rounded to an integer). </p>

<p>So you can generate a uniform random 2-out digraph of size n/c_k, and check the size of the largest SCC. If its size is not exactly n, just try again until success. The expected number of trials needed is \sqrt{n}. And generating each digraph should be done in O(n) time. So in total the algorithm has expected running time O(n^{3/2}). See <a href="http://arxiv.org/pdf/1504.06238v1.pdf" rel="nofollow">this paper</a> for more details.</p>
What is the algorithm for generating a random Deterministic Finite Automata?
<p>The DFA must have the following four properties:</p>

<ul>
<li><p>The DFA has N nodes</p></li>
<li><p>Each node has 2 outgoing transitions.</p></li>
<li><p>Each node is reachable from every other node.</p></li>
<li><p>The DFA is chosen with perfectly uniform randomness from all possibilities</p></li>
</ul>

<p>This is what I have so far:</p>

<ol>
<li>Start with a collection of N nodes.</li>
<li>Choose a node that has not already been chosen.</li>
<li>Connect its output to 2 other randomly selected nodes</li>
<li>Label one transition 1 and the other transition 0.</li>
<li>Go to 2, unless all nodes have been chosen.</li>
<li>Determine if there is a node with no incoming connections.</li>
<li>If so, steal an incoming connection from a node with more than 1 incoming connection.</li>
<li>Go to 6, unless there are no nodes with no incoming connections</li>
</ol>

<p>However, this is algorithm is not correct. Consider the graph where node 1 has its two connections going to node 2 (and vice versa), while node 3 has its two connection going to node 4 (and vice versa). That is something like:</p>

<p>1 &lt;==> 2</p>

<p>3 &lt;==> 4</p>

<p>Where, by &lt;==> I mean two outgoing connections both ways (so a total of 4 connections). This seems to form 2 cliques, which means that not every state is reachable from every other state.</p>

<p>Does anyone know how to complete the algorithm?  Or, does anyone know another algorithm?  I seem to vaguely recall that a binary tree can be used to construct this, but I am not sure about that.</p>