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 ≤100000,0≤M ≤300000
数据已加强！
题解
Tarjan缩点
讨论一下入度出度就可以了
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
struct edge
{
int END, next;
} v[1000005], E[1000005];
int first[100005], Efirst[100005], p, Ep;
void add(int a, int c)
{
v[p].END = c;
v[p].next = first[a];
first[a] = p++;
}
void add1(int a, int c)
{
E[Ep].END = c;
E[Ep].next = Efirst[a];
Efirst[a] = Ep++;
}
int S[100005];
int low[100005], dfsn[100005], Index;
bool flag[100005];
int T;
int belong[100005];
stack<int> st;
void tarjan(int rt)
{
low[rt] = dfsn[rt] = ++Index;
st.push(rt);
flag[rt] = 1;
for (int i = first[rt]; i != -1; i = v[i].next)
{
if (!dfsn[v[i].END])
{
tarjan(v[i].END);
low[rt] = min(low[rt], low[v[i].END]);
}
else if (flag[v[i].END])
low[rt] = min(low[rt], dfsn[v[i].END]);
}
if (dfsn[rt] == low[rt])
{
T++;
int v;
do
{
v = st.top();
st.pop();
flag[v] = 0;
belong[v] = T;
S[T]++;
} while (dfsn[v] != low[v]);
}
}
int isnroot[100005], ithason[100005];
int main()
{
memset(first, -1, sizeof(first));
memset(Efirst, -1, sizeof(Efirst));
//freopen("killer.in", "r", stdin);
//freopen("killer.out", "w", stdout);
int n, m;
int s, e;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &s, &e);
add(s, e);
}
for (int i = 1; i <= n; i++)
if (!dfsn[i])
tarjan(i);
for (int i = 1; i <= n; i++)
{
for (int j = first[i]; j != -1; j = v[j].next)
{
if (belong[i] != belong[v[j].END])
{
add1(belong[i], belong[v[j].END]);
isnroot[belong[v[j].END]]++;
ithason[belong[i]]++;
}
}
}
int ans = 0;
bool flags = 0;
for (int i = 1; i <= T; i++)
{
if (!isnroot[i])
{
ans++;
if (flags)
continue;
//if (!ithason[i])
// flags = 1;
if (S[i] == 1)
{
if (!ithason[i])
flags = 1;
else
{
bool e = 0;
for (int j = Efirst[i]; j != -1; j = E[j].next)
{
if (isnroot[E[j].END] == 1)
e = 1;
}
if (!e)
flags = 1;
}
}
}
}
// if (!ans)
// ans = 1;
if (flags)
ans -= 1;
printf("%.6lf", (double)(n - ans) / n);
}