Experiments
-----------

We will make uniform graph process until generate 3000 forests with 2n nodes and n edges, n = 5, 50, 500, and 5000.
In a process we start with 2n isolated nodes: 1,2, ... 2n, and determine "random edges" (u,v). If (u,v) does not
make a cycle we add (u,v) to the graph. If a cycle is detected the current process is stopped, we increment
the number of trials, and a new process begins. If (u,v) is not in a cycle and the number of included edges is n, we
increment the number of generated forests adding the number of trials to s. Thus, at the end s is the sum of the number
of trials to find 3000 forests, and s/3000 should be approximately equal to "ev" the expected value of the
number of trials until a process ends with a forest of n edges. Results:


Experiment 1.  2n = 10 nodes, n = 5 edges, ev = 2.38. 
    ---------- -------------
    number of |experimental |
    forests   |        data |
    ----------+-------------+
          100 |        2.25 |
          500 |        2.46 |
         1000 |        2.43 |
         1500 |        2.42 |
         2000 |        2.42 |
         2500 |        2.42 |
         3000 |        2.41 |
                             

Experiment 2.  2n = 100 nodes, n = 50 edges, ev = 3.36. 
    ----------+-------------
    number of |experimental |
    forests   |        data |
    ----------+-------------
          100 |        3.51 |             
          500 |        3.39 |             
         1000 |        3.38 |             
         1500 |        3.41 |             
         2000 |        3.42 |             
         2500 |        3.43 |             
         3000 |        3.46 |     


Experiment 3.  2n = 1000 nodes, n = 500 edges, ev = 4.89. 
    ---------- -------------
    number of |experimental | 
    forests   |        data |       
    ---------- -------------
          100 |        5.78 |
          500 |        5.14 |
         1000 |        5.02 |
         1500 |        4.90 |
         2000 |        4.87 |
         2500 |        4.86 |
         3000 |        4.86 | 


Experiment 4.  2n = 10000 nodes, n = 5000 edges, ev = 7.16.
    ---------- -------------
    number of |experimental |
    forests   |        data |
    ---------- -------------
          100 |        6.73 |
          500 |        6.95 |
         1000 |        7.37 | 
         1500 |        7.25 | 
         2000 |        7.13 | 
         2500 |        7.18 | 
         3000 |        7.19 | 
                              

Union-find is the standard algorithm to detect cycles. The union-find problem [see the Manber reference,
(available in WEB)] is the following:
There are N elements: x_1, x_2, ...,x_N. The elements are divided into groups (components in our case).
Initially each element (node) is in a component by itself. There are two kinds of operations performed on the
nodes and the components in any arbitrary order:
Operation find(u): returns the name of the component that contains u,
union(find(u), find(v)): combines component that contains u with component that contains v to form a new
component with a unique name.

PARI code
---------
global id \\ union-find structure
global sz

init(N) = { id = vectorsmall(N); sz = vectorsmall(N);
for(i = 1, N, id[i] = i; sz[i] = 1)};

find(i) = { while(i != id[i], id[i] = id[id[i]]; i = id[i]); i };

union(i, j) = { if(sz[i] < sz[j], id[i] = j; sz[j] += sz[i]
, id[j] = i; sz[i] += sz[j]) };

Simulation(n) = {my(nForests = 0, forest, u, v, r1, r2, s = 0, nTrials = 0);
until(nForests == 3000,
   init(2*n); forest = 1;
   for(m = 1, n,
      u = random(2*n) + 1; v = random(2*n)+1;
      r1 = find(u); r2 = find(v);
      if(r1 == r2, forest = 0; break());
      union(r1, r2)
      );
   nTrials++;
   if(forest,
      nForests++;
      s += nTrials;
      nTrials = 0;
      if(nForests % 100 == 0, print(nForests "    " 1. * s/nForests))
      )
   )
};