题目描述

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 ≤ 10 0000,0≤M ≤ 30 0000

题目分析

首先将原DAG进行缩点
那么每个联通块只要问一次
那么答案就是1-(ans/n),ans是强连通分量个数
但是还要注意这个情况：
入度为零，大小为1的强连通分量，且这个单点的所有出边指向的点所在的强连通分量 入度都大于等于2
若有这样的点 ans要-- 意思是说可以少询问一个人

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tot,color,tim;
int head[100100*2],net[601000*2],to[601000*2];
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y; }
int deep[100100],belong[100100],low[100100],num[100100];
int vis[100100],sta[100100];
void tarjan(int x)
{
    deep[x]=low[x]=++tim;
    sta[++sta[0]]=x,vis[x]=1;
    for(int i=head[x];i;i=net[i])
    {
        if(!deep[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
        else if(vis[to[i]]) low[x]=min(low[x],deep[to[i]]);
    }
    if(deep[x]==low[x])
    {
        int tmp;
        color++;
        do
        {
            tmp=sta[sta[0]--];
            vis[tmp]=0;
            belong[tmp]=color;
            num[color]++;        
        }while(tmp!=x);
    }
}
int visit[100100],ru[100100];
int check(int x)
{
    for(int i=head[x];i;i=net[i])
        if(ru[to[i]-n]==1) return 0;
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int x,y,i=1;i<=m;i++)
        scanf("%d%d",&x,&y),add(x,y);
    for(int i=1;i<=n;i++) if(!deep[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=net[j])
            if(belong[i]!=belong[to[j]]&&visit[belong[to[j]]]!=belong[i])
                visit[belong[to[j]]]=belong[i],ru[belong[to[j]]]++,add(belong[i]+n,belong[to[j]]+n);
    int ans=0;
    for(int i=1;i<=color;i++) if(!ru[i]) ans++;
    for(int i=1;i<=color;i++)
        if(!ru[i]&&num[i]==1&&check(i+n)) { ans--; break; }
    printf("%.6lf",(1.0*n-ans)/n);
    return 0;
}