题目链接

传送门

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

题解

首先考虑强连通分量
对于一个强连通分量 所有的点都相连
最优的询问对象是,把强连通分量缩成一个点(问其中一个可推出所有,只要不第一次问就是罪犯可以一直安全),问那些入度为0的(这里相当于再把连通的缩为一个点)。
这个时候我们剩下了好多点集
考虑答案是什么

发现分母全都可以约掉(s表示每个点集)
最终发现 tot为点集个数,也就是缩点后入度为0的点。
有一个特殊情况就是 当你发现有一个点集只有一个点并且入度为0并且不影响其它点入度是否为0 这样的话当你知道了剩余的所有点的时候这个也知道了 这个时候ans--

代码