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; }
