Description

一位冷血的杀手潜入 Na-wiat, 并假装成平民. 警察希望能在 \(n\) 个人里面, 查出谁是杀手.

警察能够对每一个人进行查证, 假如查证的对象是平民, 他会告诉警察, 他认识的人, 谁是 杀手, 谁是平民. 假如查证的对象是杀手, 杀手将会把警察干掉.

现在警察掌握了每一个人认识谁.

每一个人都有可能是杀手, 可看作他们是杀手的概率是相同的.

问: 根据最优的情况, 保证警察自身安全并知道谁是杀手的概率最大是多少?

Input

第一行有两个整数 \(n, m\). 接下来有 \(m\) 行, 每行两个整数 \(x, y\), 表示 \(x\) 认识 \(y\) (\(y\) 不一定认识 \(x\)) .

Output

仅包含一行一个实数, 保留小数点后面 \(6\) 位, 表示最大概率.

Sample Input

5 4
1 2
1 3
1 4
1 5

Sample Output

0.800000

Data Range

对于 100% 的数据有 \(1 \leq n \leq 100000, 0 \leq m \leq 300000\)

Explanation

我们发现如果存在一个强连通分量, 那么这个强连通分量从哪里进去都等效 (只要第一个不是杀手). 然后我们可以进一步推断出, 如果一个强连通分量的入度大于 \(1\), 也就是说 不止一个点指向它, 则整个强连通分量都是安全的了.

于是我们先预处理出强连通分量, 然后直接搞一下入度就可以了.

最后答案是 \(\frac{n - k}{n}\).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 100100, maxm = 300100;

class Graph
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
};

class StronglyConnectedComponents : public Graph
{
public:
    stack<int> stk;
    int instk[maxn], dfn[maxn], low[maxn];
    int dcnt, bcnt;
    int belong[maxn], bsize[maxn];
    void dfs(int p)
    {
        low[p] = dfn[p] = ++dcnt;
        stk.push(p);
        instk[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            int q = ep->v;
            if (!dfn[q]) {
                dfs(q);
                if (low[q] < low[p])
                    low[p] = low[q];
            } else if (instk[q] && dfn[q] < low[p]) {
                low[p] = dfn[q];
            }
        }
        if (dfn[p] == low[p]) {
            bcnt++; // Assign new belong / block counter index
            int q = 0;
            do {
                q = stk.top();
                stk.pop();
                instk[q] = false;
                belong[q] = bcnt;
                bsize[bcnt] += 1;
            } while (q != p);
        }
        return ;
    }
    void tarjan(void)
    {
        while (!stk.empty())
            stk.pop();
        dcnt = bcnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(instk, 0, sizeof(instk));
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                dfs(i);
        return ;
    }
} scc;

class StronglyConnectedTree : public Graph
{
public:
    int in_degree[maxn];
    bool vis[maxn];
    void add_edge(int u, int v)
    {
        Graph::add_edge(u, v);
        in_degree[v] += 1;
        return ;
    }
    void clone(void)
    {
        for (int p = 1; p <= n; p++) {
            for (edge *ep = scc.edges[p]; ep; ep = ep->next) {
                int q = ep->v;
                if (scc.belong[p] != scc.belong[q] && !vis[scc.belong[q]]) {
                    vis[scc.belong[q]] = true;
                    add_edge(scc.belong[p], scc.belong[q]);
                }
            }
            for (edge *ep = scc.edges[p]; ep; ep = ep->next) {
                int q = ep->v;
                if (scc.belong[p] != scc.belong[q])
                    vis[scc.belong[q]] = false;
            }
        }
        return ;
    }
    bool judge(int p)
    {
        if (in_degree[p] != 0 || scc.bsize[p] != 1)
            return false;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (in_degree[ep->v] == 1)
                return false;
        return true;
    }
} sct;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    scc.n = sct.n = n;
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        scc.add_edge(u, v);
    }
    scc.tarjan();
    sct.clone();
    int res = 0;
    for (int i = 1; i <= scc.bcnt; i++)
        if (sct.in_degree[i] <= 0)
            res += 1;
    for (int i = 1; i <= scc.bcnt; i++)
        if (sct.judge(i)) {
            res -= 1;
            break;
        }
    llf f_res = (llf)(n - res) / n;
    printf("%.6lf\n", f_res);
    return 0;
}