【问题描述】
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，
查出谁是杀手。
警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他
认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多
少？
对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000
【分析】
很简单的一道题。题目给了一个有向图，每查未知的一个人，猜错的概率增加1/n。如果出现环的话，那么我们只要在环上任意找一点，只要这人不是杀手，就可以直接推出整个环，也就是说一个环上猜错的概率只有1/n。然后我们就可以先强连通缩点。
缩点以后，一个人是不是杀手可以由认识他的人（前继）推过来，因此我们可以先选入度为0的点，也只有这些点会有1/n的概率猜错。这样直接算出缩点后入度为0的点就行了。
值得注意的是，有一个需要特判的情况，如下数据：
3 1
1 2
这时入度为0的点有两个，也就是答案是1⁄3，但实际上我们只要判断玩1，2就能直接知道3是不是杀手，所以3不可能猜错，正确答案是2/3。最后判断一下是否存在大小为1的强连通分量然后-1就行了。
【代码】
/**************************************************************
Problem: 2438
User: N_C_Derek
Language: C++
Result: Accepted
Time:716 ms
Memory:19260 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int v,next;
}e[];
int n,m,et,ct,st,Index;
int d[],first[],s[],back_up[][],color[],dfn[],low[],num[];
bool p[],instack[];
void insert(int x,int y)
{
e[++et].v = y;
e[et].next = first[x];
first[x] = et;
}
void dfs(int x)
{
dfn[x] = low[x] = ++Index;
instack[x] = true;
s[++st] = x;
for (int i = first[x];i ;i = e[i].next)
{
if (!dfn[e[i].v])
{
dfs(e[i].v);
low[x] = min(low[x],low[e[i].v]);
}
else if (instack[e[i].v])
low[x] = min(low[x],dfn[e[i].v]);
}
if (dfn[x] == low[x])
{
ct ++;
do
{
color[s[st]] = ct;
instack[s[st]] = false;
num[ct] ++;
st --;
} while (s[st + ] != x);
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(dfn,,sizeof(dfn));
for (int i = ;i <= m;i ++)
{
int x,y;
scanf("%d %d",&x,&y);
back_up[i][] = x,back_up[i][] = y;
insert(x,y);
}
for (int i = ;i <= n;i ++)
if (!dfn[i])
dfs(i);
for (int i = ;i <= m;i ++)
if (color[back_up[i][]] != color[back_up[i][]])
d[color[back_up[i][]]] ++;
int ans = ;
for (int i = ;i <= ct;i ++)
if (d[i] == )
ans++;
for (int i = ;i <= ct;i ++)
if (ans > && d[i] == && num[i] == )
{ans --;break;}
printf("%.6lf", - (double)ans / n);
}