题意简述

有一张 \(n\) 个节点的无边图，图在连通之前每次随机抽取一个点然后建边，求期望操作次数（即最大多少次）。

思路

这道题似乎和图论没什么关系，首先我们看 \(n\) 个球抽出一个的概率是 \(\frac{1}{n}\) ，那么抽第二个时概率是 \(\frac{1}{n-1}\) 以此类推。所以最坏情况下就是抽第 \(n-1\) 个球是都没有抽到，所以我们就只需要把 \(1\) 到 \(n-1\) 每个球抽中的概率加起来就行了。

code

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	double ans=0.0;
	for(double i=1;i<n;i++) ans+=(double)n/(n-i);
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}