C++(g++ 7.5.0) 解法, 执行用时: 199ms, 内存消耗: 7328K, 提交时间: 2022-08-22 10:43:45

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int to,nx;
}p[maxn*3];
struct node2
{
    int to,nx;
}q[maxn*3];
int n,m,dfn[maxn],low[maxn],head[maxn],tot,vis[maxn],scc[maxn],cnt,sz[maxn],d[maxn],head2[maxn];
double ans;
void addedge(int s,int t)
{
    p[++tot].to=t,p[tot].nx=head[s],head[s]=tot;
}
void addedge2(int s,int t)
{
    d[t]++;
    q[++tot].to=t,q[tot].nx=head2[s],head2[s]=tot;
}
stack<int>sk;
void tarjan(int cur)
{
    dfn[cur]=low[cur]=++tot;
    sk.push(cur);
    vis[cur]=1;
    for(int i=head[cur];i;i=p[i].nx)
    {
        int to=p[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[cur]=min(low[cur],low[to]);     }
            else if(!scc[to]) low[cur]=min(low[cur],dfn[to]);
    }
    if(dfn[cur]==low[cur])
    {
        int now;
        cnt++;
        do
        {
            now=sk.top();
            sk.pop();
            vis[now]=0;
            scc[now]=cnt;
            sz[cnt]++;
        }while(now!=cur);
    }
}
int ok(int cur)
{
    if(d[cur]||sz[cur]!=1) return 0;
    for(int i=head2[cur];i;i=q[i].nx)
    {
        if(d[q[i].to]==1) return 0;
    }
    return 1;
}
void rebuild()
{
     
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=p[j].nx)
        {
            if(scc[i]!=scc[p[j].to]) addedge2(scc[i],scc[p[j].to]);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        addedge(u,v);
         
    }
    tot=0;
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    tot=0;
    rebuild();
    for(int i=1;i<=cnt;i++)
    {
        if(!d[i]) ans++;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(ok(i))
        {
            ans--;
            break;
        }
    }
    printf("%.6f",(double)(n-ans)/(double)n);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 194ms, 内存消耗: 8052K, 提交时间: 2023-06-21 23:43:37

#include<bits/stdc++.h>
using namespace std;
int dfn[300005],lw[300005],h[300005],hh[300005],inv[300005],c[300005],st[300005],sze[300005],n,m,tot,cnt,top,u,v,C,dc,vis[300005],vv[300005],ff=1,pp=1;
struct asdf{int v,nxt;}e[600005],ee[600005];
struct asd{int u,v;}E[300005];
void ad(int u,int v){e[++tot].v=v;e[tot].nxt=h[u];h[u]=tot;}
void ae(int u,int v){ee[++tot].v=v;ee[tot].nxt=hh[u];hh[u]=tot;inv[v]++;}
void tarjan(int np){
	dfn[np]=lw[np]=++dc;
	st[++top]=np;vis[np]=1;
	for(int i=h[np];i;i=e[i].nxt){
		if(!dfn[e[i].v])tarjan(e[i].v),lw[np]=min(lw[np],lw[e[i].v]);
		else if(vis[e[i].v]&&dfn[e[i].v]<lw[np])lw[np]=dfn[e[i].v];
	}
	if(lw[np]==dfn[np]){C++;while(st[top+1]-np)vis[st[top]]=0,c[st[top]]=C,sze[C]++,top--;}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>E[i].u>>E[i].v,ad(E[i].u,E[i].v);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	tot=1;
	for(int i=1;i<=n;i++){
		for(int j=h[i];j;j=e[j].nxt)if(c[i]-c[e[j].v]&&!vv[c[e[j].v]])ae(c[i],c[e[j].v]),vv[c[e[j].v]]=1;
		for(int j=h[i];j;j=e[j].nxt)vv[c[e[j].v]]=0;
	}
	for(int i=1;i<=C;i++){
		if(!inv[i])cnt++;
		if(ff&&!inv[i]&&sze[i]<2){pp=1;for(int j=hh[i];j;j=ee[j].nxt)if(inv[ee[j].v]<2){pp=0;break;}if(pp)cnt--,ff=0;}
	}
	printf("%.6lf",(double)(n-cnt)/n);
    return 0;
}