Rt,代码如下

#include <bits/stdc++.h>
#define stack stack_
using namespace std;
const int maxn=100005;
const int maxm=300005;
int n,m,cnt,sum,ans,top;
int head[maxn],dfn[maxn],low[maxn],siz[maxn],col[maxn],stack[maxn],deg[maxn];
bool ins[maxn],flag[maxn];
struct edge{
	int v,nxt;
}a[maxm<<1];
void add(int x,int y){
	++cnt;
	a[cnt].v  =y;
	a[cnt].nxt=head[x];
	head[x]=cnt;
}
inline int read(){
	int ret=0,f=1;	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f; 
}
void scan(){
	int k,j,i;
	n=read();	m=read();
	for(k=1;k<=m;k++){
		int x,y;
		x=read();	y=read();
		add(x,y);
	}
}
void tarjan(int x){
	int k,j,i;
	stack[++top]=x;	dfn[x]=low[x]=++cnt;
	for(k=head[x];k;k=a[k].nxt){
		int v=a[k].v;
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else	if(!ins[v])low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
		int y;	sum++;
		do{
			y=stack[top--];	ins[y]=1;	col[y]=sum;	siz[sum]++;
		}while(x!=y);
	}
}
void prework(){
	int k,j,i;
	cnt=0;
	for(k=1;k<=n;k++)
	if(!dfn[k])	tarjan(k);
}
void solve(){
	int k,j,i;
	for(k=1;k<=n;k++){
		for(j=head[k];j;j=a[j].nxt){
			int v=a[j].v;
			if(col[k]==col[v])	continue;
			deg[col[v]]++;
		}
	}
	for(k=1;k<=n;k++)
	if(!deg[col[k]]&&siz[k]==1&&!flag[col[k]]){
		for(j=head[k];j;j=a[j].nxt){
			int v=a[j].v;
			if(col[k]==col[v])	continue;
			if(deg[col[v]]==1){
				flag[col[k]]=1;
				break;
			}
		}
	}
	else	flag[col[k]]=1;
	bool pd=0;
	for(k=1;k<=sum;k++){
		if(!flag[k])	pd=1;
		if(!deg[k])	ans++;
	}
	ans-=pd;
	printf("%.6lf\n",1.0-1.0*ans/n);
}
int main(){
	int k,j,i;
	scan();	prework();	solve();
	return 0;
}