Description
一位冷血的殺手潛入 Na-wiat，並假裝成平民。警察希望能在 N 個人裡面，查出誰是殺手。
警察能夠對每一個人進行查證，假如查證的對象是平民，他會告訴警察，他認識的人， 誰是殺手， 誰是平民。 假如查證的對象是殺手， 殺手將會把警察干掉。 現在警察掌握了每一個人認識誰。 每一個人都有可能是殺手，可看作他們是殺手的概率是相同的。
問：根據最優的情況，保證警察自身安全並知道誰是殺手的概率最大是多少？
Input
第一行有兩個整數 N,M。
接下來有 M 行，每行兩個整數 x,y，表示 x 認識 y（y 不一定認識 x,例如胡錦濤同志） 。
Output
僅包含一行一個實數，保留小數點後面 6 位，表示最大概率。
題解
一開始看到這個題還以為是關於概率和期望的問題，，結果發現這題的概率就是個沒有技術含量的東西，，假如警察一共只詢問了x個人的話，那麼安全的概率就是1-x/n，，所以說關鍵就是求出x的值；
我們發現如果將所有關系看作一棵樹的話，那麼我們只要調查樹的根節點就可以了，也就是說我們的答案就是1-根節點數/節點總數；但是我們發現這個有向圖並不是一棵樹，而是有環存在的，這樣我們就無法將圖轉換成一棵樹，，這時我們可以考慮縮點，，因為如果關系構成環的話，那麼我們調查環內的任何一個節點都可以將整個環調查出來，也就是說對於整個環，我們只需算作一次調查，所以我們可以將環用Tarjan算法縮成一個點，這樣整個圖就變成了一個有向無環圖，即一棵樹，然後我們將圖遍歷一遍，求出入度為1的節點（即根節點）個數，然後算出答案即可。
還需要注意一個問題，由於題目的關系，我們可以知道如果最後只剩一個點沒有調查，那麼可以直接確定這個點的身份，就不用再次調查一遍了。那麼這個單點應該怎麼確定呢？首先它的入度要為0，其次它的出邊所連的點應該可以包含在其他子樹中（也就是相連點的入度大於1），那麼這個點就可以放到最後，先詢問其他點，這樣最後這個點的身份也就確定了。所以如果我們發現有這樣的點的話，令根節點數減1就可以了。
代碼如下
#include
#include
#include
#include
#include
#define INF INT_MAX/2
#define N 100010
#define M 300010
using namespace std;
struct Edge { int to,next;Edge() { next=to=0; } }edge[M];
double ans=1;int v[N],b[N],in[N]; //v[]表示該點是否訪問過，b[]表示該點是否在棧中
int n,m,dl[N],top,low[N],dfn[N],t,to[N],head[N],tot;
int input() {
char c=0;int s=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
return s;
}
void Add_edge(int a,int b) {
Edge &e=edge[tot];e.to=b,e.next=head[a];head[a]=tot++;
}
void reduce(int p) {
while(top>=p) {
b[dl[top]]=false;
to[dl[top--]]=dl[p]; //to[]為該元素所屬的強聯通分量
} return;
}
int dfs(int now) {
if(b[now]) return low[now]; if(v[now]) return INF;
v[now]=b[now]=true;low[now]=dfn[now]=++t;
int o;dl[o=++top]=now;
for(int i=head[now];i!=-1;i=edge[i].next) {
low[now]=min(low[now],dfs(edge[i].to));
}
if(low[now]==dfn[now]) reduce(o); return low[now];
}
void Tarjan() {
for(int i=1;i<=n;i++) if(v[i]==false) dfs(i);
}
void work() {
memset(v,0,sizeof(v)); //v[]在此函數中為強聯通分量的元素個數
bool c=false;for(int i=1;i<=n;i++) {
for(int j=head[i];j!=-1;j=edge[j].next)
if(to[i]!=to[edge[j].to])
in[to[edge[j].to]]++; //統計強連通分量入度
if(to[i]!=i) v[to[i]]++; //統計該強連通分量的元素個數
}
int s=0;for(int i=1;i<=n;i++) { //s為根節點的個數
if(to[i]==i&&!in[i]) {
s++; if(c==false&&!v[i]) {
int j=-1;
for(j=head[i];j!=-1;j=edge[j].next) {
if(in[edge[j].to]==1) { break; }
}
if(j==-1) c=true;
}
}
}
if(c==true) ans-=(s-1)/(double)n;
else ans-=s/(double)n;
}
int main() {
n=input();m=input();int a,b;memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++) { a=input(),b=input();Add_edge(a,b); }
Tarjan(); work(); printf("%.6lf",ans); return 0;
}
