Yifan Wu's Blog

#include<cstdio>
#include<cstring>
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
const int N = 100001;
const int M = 300100;
int head[N] , next[M] , end[M];
void addedge(int a , int b)
{
    static int q = 1;
    end[q] = b;
    next[q] = head[a];
    head[a] = q++;
}
int belong[N] , size_scc[N] , now , dfn[N] , low[N] , time_clock;
bool ext[N] , instack[N];
int stack[N] , top;
inline void dfs(int x)
{
    int j;
    dfn[x] = low[x] = ++time_clock;
    stack[++top] = x;
    instack[x] = 1;
    ext[x] = 1;
    for(j = head[x] ; j ; j = next[j])
    {
        if (!ext[end[j]])
        {
            dfs(end[j]);
            low[x] = _min(low[x] , low[end[j]]);
        }
        else if (instack[end[j]])
            low[x] = _min(low[x] , dfn[end[j]]);
    }
    if (low[x] == dfn[x])
    {
        ++now;
        while(1)
        {
            //i = S.top();
            belong[stack[top]] = now;
            instack[stack[top]] = 0;
            ++size_scc[now];
            if (dfn[stack[top]] == low[stack[top]])
            {
                --top;
                break;
            }
            --top;
        }
    }
}
int in[N];
int main()
{
    //freopen("fig8.in" , "r" , stdin);
    int n , m;
    scanf("%d%d" , &n , &m);
    int a , b;
    register int i , j;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d" , &a , &b);
        addedge(a , b);
    }
    for(i = 1 ; i <= n ; ++i)
        if (!ext[i])
            dfs(i);
    for(i = 1 ; i <= n ; ++i)
    for(j = head[i] ; j ; j = next[j])
        if (belong[i] != belong[end[j]])
            ++in[belong[end[j]]];
    int ans = 0;
    for(i = 1 ; i <= now ; ++i)
        if (!in[i])
            ++ans;
    for(i = 1 ; i <= now ; ++i)
        if (ans > 1 && size_scc[i] == 1 && in[i] == 0)
        {
            --ans;
            break;
        }
    printf("%.6lf" , 1 - double(ans) / n);
    return 0;
}