[文章目录]
Description
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。 警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。 现在警察掌握了每一个人认识谁。 每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。 问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？ 1≤N ≤100000,0≤M≤300000
首先，如果问到一个人，由于那个人会告诉你一些平民，所以可以一直问下去。
tarjan缩点，发现就是将入度为零的分量都各问一个人就好了。
特殊情况：如果有一个人，自己就是强联通分量，并且其所有指向的强联通分量都可以通过别的方式被问到，那么就没有必要问这类人中的一个了。可以通过排除法判断一个这样的人。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,fna;
int head[N<<1],to[N<<3],nxt[N<<3],cnt;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int dfn[N],low[N],z[N],top,tot,ans,bel[N],rd[N],num[N];
bool inz[N];
void tarjan(int x)
{
low[x]=dfn[x]=++tot;
z[++top]=x; inz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(inz[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
ans++; int t;
do
{
t=z[top--];
inz[t]=0;
bel[t]=ans;
num[ans]++;
}while(t!=x);
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,k,x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=nxt[j])
if(bel[i]!=bel[to[j]])
{
add(bel[i]+n,bel[to[j]]+n);
rd[bel[to[j]]]++;
}
}
bool flag=0;
for(int i=1;i<=ans;i++)
{
if(!rd[i])
{
fna++;
if(num[i]==1)
{
bool fl=1;
for(int j=head[i+n];j;j=nxt[j])
if(rd[to[j]-n]==1) fl=0;
flag=flag|fl;
}
}
}
printf("%.6lf",1.0*(n-fna+flag)/n);
return 0;
}