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

HINT#

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警 察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概 率是0.8。

对于 100%的数据有 1≤N ≤100000,0≤M ≤300000 数据已加强！

题解#

Tarjan缩点 讨论一下入度出度就可以了

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
struct edge
{
    int END, next;
} v[1000005], E[1000005];
int first[100005], Efirst[100005], p, Ep;
void add(int a, int c)
{
    v[p].END = c;
    v[p].next = first[a];
    first[a] = p++;
}
void add1(int a, int c)
{
    E[Ep].END = c;
    E[Ep].next = Efirst[a];
    Efirst[a] = Ep++;
}
int S[100005];
int low[100005], dfsn[100005], Index;
bool flag[100005];
int T;
int belong[100005];
stack<int> st;
void tarjan(int rt)
{
    low[rt] = dfsn[rt] = ++Index;
    st.push(rt);
    flag[rt] = 1;
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (!dfsn[v[i].END])
        {
            tarjan(v[i].END);
            low[rt] = min(low[rt], low[v[i].END]);
        }
        else if (flag[v[i].END])
            low[rt] = min(low[rt], dfsn[v[i].END]);
    }
    if (dfsn[rt] == low[rt])
    {
        T++;
        int v;
        do
        {
            v = st.top();
            st.pop();
            flag[v] = 0;
            belong[v] = T;
            S[T]++;
        } while (dfsn[v] != low[v]);
    }
}
int isnroot[100005], ithason[100005];
int main()
{
    memset(first, -1, sizeof(first));
    memset(Efirst, -1, sizeof(Efirst));
    //freopen("killer.in", "r", stdin);
    //freopen("killer.out", "w", stdout);
    int n, m;
    int s, e;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &s, &e);
        add(s, e);
    }
    for (int i = 1; i <= n; i++)
        if (!dfsn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
    {
        for (int j = first[i]; j != -1; j = v[j].next)
        {
            if (belong[i] != belong[v[j].END])
            {
                add1(belong[i], belong[v[j].END]);
                isnroot[belong[v[j].END]]++;
                ithason[belong[i]]++;
            }
        }
    }
    int ans = 0;
    bool flags = 0;
    for (int i = 1; i <= T; i++)
    {
        if (!isnroot[i])
        {
            ans++;
            if (flags)
                continue;
            //if (!ithason[i])
            //    flags = 1;
            if (S[i] == 1)
            {
                if (!ithason[i])
                    flags = 1;
                else
                {
                    bool e = 0;
                    for (int j = Efirst[i]; j != -1; j = E[j].next)
                    {
                        if (isnroot[E[j].END] == 1)
                            e = 1;
                    }
                    if (!e)
                        flags = 1;
                }
            }
        }
    }
    // if (!ans)
    //     ans = 1;
    if (flags)
        ans -= 1;
    printf("%.6lf", (double)(n - ans) / n);
}