徐老师的村庄拯救计划
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在追查一个连环杀人案的杀人凶手
最终锁定了这个凶手藏在一个偏僻村庄里，这个村庄里一共有 $n$ 个村民
这 $n$ 个村民早就发现最近村子不太正常，早就开始互相偷偷调查了
现在徐老师通过一些常人不能发现的蛛丝马迹，已经确定了哪些人调查过哪些人
这里我们认为如果 $x$ 调查过 $y$，那么 $x$ 会知道 $y$ 的身份，同时 $x$ 也会得到 $y$ 调查过的所有人的身份（这里我们认为调查不存在时间关系，只要 $x$ 调查过 $y$，最终一定会得知 $y$ 所知道的所有人的身份）
并且请注意，调查是偷偷进行的，所以 $x$ 调查了 $y$ 不代表 $y$ 知道 $x$ 的信息
现在徐老师打算选择几位村民谈话，来获取他们手里的信息
显然如果徐老师谈话的是好人，那么这个人一定会把自己知道的所有信息告诉徐老师
但是如果徐老师刚好谈话的是这个杀人凶手，就有可能遇到危险
现在徐老师想知道，在运气最好的情况下，找到凶手并且不会遇到危险的概率最大是多少？
P.S. 显然，徐老师找的人越多，遇到危险的概率就越大，但是徐老师的运气非常好，他找的人只要存在不是凶手的可能性，就一定不是凶手
输入格式
第一行包含两个整数 $n,m$，表示村庄有 $n$ 个村民，并且存在 $m$ 次调查
接下来 $m$ 行，每行包含两个整数 $x,y$ 表示 $x$ 调查过 $y$
对于 $30\%$ 的数据，满足 $1 \leq n, m \leq 10^3$。
对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 10^5$。
输出格式
输出一个小数表示概率，保留 $6$ 位小数
样例
5 4
1 2
1 3
1 4
1 50.800000提示
找 $1$ 调查即可，这样只需要查 $1$ 个人就可以知道凶手是谁
2023暑CSP-S复赛集训模拟赛三
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-30 22:15
- 结束于
- 2023-8-9 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 22
