【洛谷p4819】[中山市选]杀人游戏 #Tarjan+概率#

#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define R register

/*【p4819】杀人游戏
有一个杀手，每个平民知道一些人的身份：杀手或平民。
每个人成为杀手的可能性相同。求能确定杀手的概率。*/

//Tarjan缩点，缩点之后只需查询环中的一个人、就可以知道整个环的信息。
//=>入度为0的点的个数 就是 查不出来的杀手的人数。

//注意：如果知道了N-1个人的身份，那么剩下的那个人一定是杀手（排除法）。
//=>寻找一个大小为1且入度为0的点（缩点后，‘与世隔绝’的杀手），
//并且他指向的点入度不为1，说明可以从别的点反推排除，则标记flag=1。

//若flag==1,ans=1-(缩点后入度为0的点-1)/n;
//若flag==0,ans=1-(缩点后入度为0的点)/n.

void reads(int &x){ //读入优化（正负整数）
    ll f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f; //正负号
}

const int N=500019,M=500019;

int n,m,dfn[N],low[N],stack[N],vis[N];
 
int dfn_=0,top_=0,sum=0,col[N],siz[N];

int u[M],v[M],head[N],tot=0,rd[N],flag=0,ans=0;

struct node{ int ver,nextt; }e[M];

inline void add(R int x,R int y){ 
    e[++tot].nextt=head[x],e[tot].ver=y,head[x]=tot; 
}

inline void tarjan(int x){
    dfn[x]=low[x]=++dfn_,stack[++top_]=x,vis[x]=1;
    for(R int i=head[x];i;i=e[i].nextt){
        if(!dfn[e[i].ver]) tarjan(e[i].ver),low[x]=min(low[x],low[e[i].ver]);
        else if(vis[e[i].ver]) low[x]=min(low[x],dfn[e[i].ver]);
    } if(dfn[x]==low[x]){
        col[x]=++sum; siz[sum]++; vis[x]=0;
        while(stack[top_]!=x){ //x上方的节点是可以保留的
            col[stack[top_]]=sum,siz[sum]++;
            vis[stack[top_]]=0,top_--;
        } top_--; //col数组记录每个点所在连通块的编号
    }
}

int main(){
    reads(n),reads(m);
    for(R int i=1;i<=m;i++)
        reads(u[i]),reads(v[i]),add(u[i],v[i]);
    for(R int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    memset(head,0,sizeof(head)); tot=0; //缩点之后重新建图
    for(R int i=1;i<=m;i++) //重新连边、计算入度
        if(col[u[i]]!=col[v[i]]) rd[col[v[i]]]++,
            add(col[u[i]],col[v[i]]); //按连通块相连
    for(R int i=1;i<=sum;i++){ //缩点之后、点的个数
        if(!flag&&!rd[i]&&siz[i]==1){ //在没有找到满足FLAG的点的时候
            int okk=0; //记录是否每个出度的rd都>1
            for(R int j=head[i];j;j=e[j].nextt)
                if(rd[e[j].ver]==1) okk=-1;
            if(okk==0) flag=1;
        } if(!rd[i]) ans++; //记录rd=0的点的个数
    } if(flag==1) ans--; //用排除法减少询问
    printf("%.6lf
",1.0-(double)ans/(double)n);
}