Slow as molasses.

ER.hs

import Data.Array
import Data.Graph
import Data.IORef
import System.Random
import Control.Monad

main = do
    graphRef <- newIORef .
      array (1, 1000) $ zip [1 .. 1000] (repeat [])
    let f = do
        graph <- readIORef graphRef
        let numEdges = length $ edges graph
            numForests = length $ scc graph
        print (numEdges, numForests)
        if numEdges < 9936 && numForests > 1
        then do
          i <- randomRIO (1, 1000)
          j <- randomRIO (1, 1000)
          unless (path graph i j) $ do
            p <- randomIO :: IO Double
            when (p < 0.05) $
              modifyIORef graphRef
                (// [(i, j : (graph ! i)), (j, i : (graph ! j))])
          f
        else return ()
    f
    graph <- readIORef graphRef
    let g (i, j) = "\t" ++ show i ++ " -> " ++ show j ++ ";\n"
        h v = "\t" ++ show v ++ ";\n"
        out = "graph {\n" ++ concatMap g (edges graph) ++ concatMap h (vertices graph) ++ "}"
    writeFile "ER.gv" out