杀人游戏
Description
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？
Input
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x） 。
Output
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
Samples
Input
5 4
1 2
1 3
1 4
1 5
Output
0.800000
Hint
警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。
对于 100%的数据有 1≤N≤100000, 0≤M≤300000
首先一读题感觉是个并查集，找fa[i] == i的点进行处理就是最优的，但仔细一想感觉很不对劲，如果是用并查集来处理的话，概率就非常难处理
这个题应该是涉及到联通块的问题，对于一个环，比如1->2 2->3 3->1的情况只需要调查其中一个点就能知道其中所有点的情况，如果是还有另外一个点比如说是4 -> 1,对于这种情况，我们就可以之调查一个点来解决
对于一个强联通的环，有两个节点指向这个环中的某个节点（比如a->1,b->3,环依然是上面由1、2、3组成的环），我们可以清楚的知道，从两个点中任意选一个就能够知道环中的情况：
情况1：杀手在环内或者是所选的点，就可以直接知道杀手的情况
情况2：杀手不在环内或者是所选的节点，那么最后一个节点一定是杀手
所以说，最后一个节点可以不处理
在处理这个提的时候要从入度为0且出度不为0的点出发，这样能够保证更优，会减少调查的次数，最大化最大概率
某节点入度为0,但是其指向的节点的入度 > 1可以在最后进行处理
如果缩点后成为一个节点（之前存在环且缩点后这个点的入度为0），在处理其他节点之后，这个环里面的元素仍然没有内处理，就需要再次花费一次操作来解决联通块里面的信息
对于独立的点，我们可以放到最后进行处理或者是不进行处理
/*** keep hungry and calm PushyTao!***/
const int maxn = 3e5 + 7;
int n, m;
struct pre
{
int u;
int v;
} a[maxn];
struct node
{
int v;
int nex;
} e[maxn];
node e2[maxn];
int head[maxn],head2[maxn];
int cnt, tot;
stack <int> st;
int col[maxn];
bool vis[maxn],visit[maxn];
int dfn[maxn], low[maxn];
int siz[maxn];
int zero,times;
int Stack[maxn],top;
void init()
{
for(int i = 1; i <= n; i++)
{
head[i] = -1;
head2[i] = -1;
}
}
void add(int u, int v)
{
e[cnt].v = v;
e[cnt].nex = head[u];
head[u] = cnt ++;
}
int inDeg[maxn];
void AddEdge(int u, int v)
{
e2[cnt].v = v;
e2[cnt].nex = head2[u];
head2[u] = cnt++;
inDeg[v] ++;/// u -> v indegree v ++
}
void tarjan(int x)
{
dfn[x] = low[x] = ++ times;
Stack[++top] = x;
visit[x] = 1;
for(int i = head[x]; ~i; i = e[i].nex)
{
if(!dfn[e[i].v])
{
tarjan(e[i].v);
if(low[e[i].v] < low[x]) low[x] = low[e[i].v];
}
else if(visit[e[i].v] && dfn[e[i].v] < low[x])
{
low[x] = dfn[e[i].v];
}
}
if(low[x] == dfn[x])
{
tot++;
while(Stack[top + 1] != x){
visit[Stack[top]] = 0;
col[Stack[top]] = tot;
siz[tot] ++;
top --;
}
}
}
int main()
{
n = read, m = read;
init();/// initialize
for(int i = 1; i <= m; i++)
{
a[i].u = read;
a[i].v = read;
add(a[i].u, a[i].v);
}
// puts("ok");
for(itn i = 1; i <= n; i++)
{
if(dfn[i] == 0) tarjan(i);
}
// puts("ok");
cnt = 0;/// reset cnt as ZERO
for(int i = 1; i <= n; i++)
{
for(int j = head[i]; ~j; j = e[j].nex)
{
if(col[i] == col[e[j].v] || vis[col[e[j].v]]) continue;
AddEdge(col[i], col[e[j].v]);
vis[col[e[j].v]] = true;/// marked as 1
}
for(int j = head[i]; ~j; j = e[j].nex)
{
vis[col[e[j].v]] = false;/// marked as 0
}
}
// puts("ok");
// cout<<tot<<endl;
int falg = 0;/// tot == the number of nodes after tarjan
for (int i = 1; i <= tot; ++i)
{
if(inDeg[i] == 0) zero ++;/// the number of nodes indegee is zero
if(inDeg[i] || siz[i] >= 2) continue;
if(falg == 0)
{
int ju = 0;
for(int j = head2[i]; ~j; j = e2[j].nex)
{
if(inDeg[e2[j].v] <= 1)
{
ju = 1;
break;
}
}
if(ju == 0) zero --, falg = 1;
}
}
// cout << zero <<endl;
printf("%.6lf\n", (double)(n - zero) / (1.0 * n));
return 0;
}