题目描述

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，

查出谁是杀手。 

警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他

认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。 

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

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

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

少？

 

输入

第一行有两个整数 N,M。 

接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如敬爱的胡爷爷） 。

 

输出

仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。

 

样例输入

5 4 1 2 1 3 1 4 1 5

样例输出

0.800000

提示

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警

察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概

率是0.8。对于 100%的数据有 1≤N ≤  10 0000,0≤M ≤  30 0000

 

【题解】

       看了提示也没参悟到调查的未知身份人越少，危险越小这个道理。虽然刚开始是有这样的意识的，但是后来走上了一条名为“推式子”的不归路，然后就……有我这样的队友，警察是非阵亡不可啊。

       所谓的概率题，除了最后结果是个double型还和概率有什么关系？！其实是个tarjan缩点题。凡是成环的，只要调查其中一个人就可以了。最关键的是其中一种特殊情况，有一个点完全孤立或有一个点没有入度且出度全都被别的点调查过，就没有调查他的必要了。考试后期想这个情况是否可行想了很久，没有个所以然。到底是在疑虑什么啊这种明显符合生活常理的情况，警察叔叔非阵亡不可+1。最大概率题，并不能拘泥于式子，毕竟大多数式子都是完全客观完全平均地选择各种方案，而这道题明显是涉及到方案选择的。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int sj=100010;int n,m,e1,e2,h[sj],l[sj],a1,a2,dfn[sj],low[sj],c[sj];int s[sj],cnt,fa[sj],bi,hz,su[sj],cd[sj],rd[sj];bool r[sj];struct B{     int ne,v,u;}b[sj*3];struct T{     int ne,v;}t[sj*3];void ad1(int x,int y){     b[e1].v=y;     b[e1].u=x;     b[e1].ne=h[x];     h[x]=e1++;}void ad2(int x,int y){     t[e2].v=y;     t[e2].ne=l[x];     l[x]=e2++;}void init(){     scanf("%d%d",&n,&m);     memset(h,-1,sizeof(h));     memset(l,-1,sizeof(l));     for(int i=1;i<=m;i++)     {        scanf("%d%d",&a1,&a2);        ad1(a1,a2);     }       for(int i=1;i<=n;i++)  fa[i]=i;}int bj(int x,int y){    return x