相关疑难解决方法(0)

这是Interviewstreet难题:

我们有一个包含N个城市的国家.每天我们选择2个城市,这样他们之间就没有道路,并且在他们之间建立了一条道路.我们以相同的概率选择每对不相邻的城市.设X是我们获得连接国家之前的天数.X的预期价值是多少？输出答案的整数部分.

他们真正要问的是随机图G(n,m)连接需要多少个边m(平均).

在编写了一个实际执行实验的程序之后,我想出了通过9/10测试的"解决方案"

$f = fopen('php://stdin', 'r');
$n = intval(fgets($f));
echo round(1.25 * $n * log($n, 10));

那么可以用一个公式来解决吗？找到随机图连通性可能性的正确方法是什么？