题目描述
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？
输入格式
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x，例如 President 同志）。
输出格式
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
输入输出样例
输入 #1复制
5 4 1 2 1 3 1 4 1 5
输出 #1复制
0.800000
说明/提示
警察只需要查证 1。假如 1 是杀手，警察就会被杀。假如 1 不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2，所以能知道谁是杀手但没被杀的概率是 0.8。
对于 100% 的数据有 1≤N≤1×105,0≤M≤3×105。
代码实现：
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl;
#define int long long
using namespace std;
const int N = 3e5 + 9;
#define MAX (int)1.1e5 // 简化宏名
struct node { int to, nxt; }; // 简化next为nxt
node e[N]; // 简化edge为e
int n, m, u, v, t, c, sm, tp, res, f, c1; // 简化各类计数变量
int h[MAX]; // 简化head为h
int df[MAX]; // 简化dfn为df
int lo[MAX]; // 简化low为lo
int st[MAX]; // 简化sta为st
int col[MAX]; // 保留col(颜色)
int in[MAX]; // 简化ind为in
int s[MAX]; // 简化siz为s
bool vis[MAX]; // 保留vis(访问标记)
// 简化add函数
void add(int u, int v) {
e[++t].to = v;
e[t].nxt = h[u];
h[u] = t;
}
// Tarjan算法保持逻辑，简化变量引用
void tarjan(int u) {
df[u] = lo[u] = ++c;
vis[u] = 1, st[++tp] = u;
for (int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!df[v]) {
tarjan(v);
lo[u] = min(lo[u], lo[v]);
} else if (vis[v]) {
lo[u] = min(lo[u], df[v]);
}
}
if (df[u] == lo[u]) {
col[u] = ++sm;
vis[u] = 0;
s[sm] = 1;
while (st[tp] != u) {
col[st[tp]] = sm;
vis[st[tp]] = 0;
--tp;
s[sm]++;
}
--tp;
}
}
int h2[MAX]; // 简化head2为h2
int ne[MAX]; // 简化Next为ne
int ve[MAX]; // 简化ver为ve
int t2 = 0; // 简化tot2为t2
// 简化Add函数
void Add(int u, int v) {
ve[++t2] = v;
ne[t2] = h2[u];
h2[u] = t2;
}
int fa[MAX]; // 保留fa(父节点)
int fs[MAX]; // 简化fasiz为fs
// 简化init函数参数
void init(int s) {
for (int i = 1; i <= s; i++) {
fa[i] = i;
fs[i] = 1;
}
}
// 路径压缩保持
int getfa(int x) {
if (x == fa[x]) return x;
return fa[x] = getfa(fa[x]);
}
// 合并操作保持
void merge(int u, int v) {
int x = getfa(u);
int y = getfa(v);
fa[y] = x;
fs[x] += fs[y];
}
signed main() {
ios::sync_with_stdio(false);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
double c1 = clock();
#endif
// 主逻辑保持，简化变量名
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
add(u, v);
}
for (int i = 1; i <= n; i++)
if (!df[i])
tarjan(i);
for (int u = 1; u <= n; u++) {
for (int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (col[u] != col[v]) {
Add(col[u], col[v]);
++in[col[v]];
}
}
}
init(sm);
for (int u = 1; u <= sm; u++) {
for (int i = h2[u]; i; i = ne[i]) {
int v = ve[i];
if (fa[v] != v) continue;
merge(u, v);
}
}
int l = 0, ly = 0; // 简化lookup为l，lonely为ly
for (int i = 1; i <= sm; i++) {
if (fa[i] == i) {
if (fs[i] > 1) ++l;
else ++ly;
}
}
if (ly) {
if (ly > 1) --ly;
else if (l) --ly;
else if (n == 1) ly = 0;
}
printf("%.6lf\n", (double)(n - l - ly) / n);
#ifdef LOCAL
double c2 = clock();
cerr << "Used Time: " << c2 - c1 << "ms" << endl;
if (c2 - c1 > 1000)
cerr << "Warning!! Time Limit Exceeded!!" << endl;
fclose(stdin);
fclose(stdout);
#endif
return 0;
}