洛谷 P4819 [中山市选]杀人游戏（tarjan缩点）

P4819 [中山市选]杀人游戏

思路分析

题意最开始理解错了(我太菜了)

把题意简化一下，就是找到可以确定杀手身份的最小的危险查看数

(就是不知道该村名的身份，查看他的身份具有危险的查看数量)，用

该数除以总人数，保留6位小数，我们将每个村名和他认识的人之间

连接一条有向边，得到一个有向图，考虑到图中带有环，因为查看一

个人的身份时我们便可以知道他认识的人的具体身份，所以针对一个

环我们只要查看任意一人的身份就可以无危险的得知剩余其他人的身

份，且只有第一次查看为危险查看，我们可以看出将环缩为点和按

环判断结果是相同的，为了节省时间，我们考虑将环缩为点，对于缩

点后的图，我们发现想要知道杀手是谁，只要满足所有入度为0的点

被查看即可，但要注意，对于缩圈后的图，假设有n个点，我们查看

了n-1个点的身份，剩下一个点的身份就不用查了。最后将其减掉即

可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=3e5+100;

inline int read(){

	int ret=0;

	int f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')

			f=-f;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		ret=ret*10+(ch^'0');

		ch=getchar();

	}

	return f*ret;

}

int dfn[maxn];

int low[maxn];

int n,m;

int cnt;

struct node{

	int nex;

	int to;

}e[maxn];

int head[maxn];

void add(int u,int v){

	cnt++;

	e[cnt].nex=head[u];

	e[cnt].to=v;

	head[u]=cnt;

}

int sti[maxn];

int vis[maxn];

int  tot;

int cnt1;

int cnt2;

int clo[maxn];

int siz[maxn];

void tarjan(int x){

	low[x]=dfn[x]=++cnt1;

	vis[x]=1;

	sti[++tot]=x;

	for(int i=head[x];i;i=e[i].nex){

		int y=e[i].to;

		if(!dfn[y]){

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

		else if(vis[y]){

			low[x]=min(low[x],dfn[y]);//只用于更新最后一个点；

		}

	}

	if(dfn[x]==low[x]){

		int now=-1;

		cnt2++;

		while(now!=x){

			now=sti[tot];

			tot--;

			vis[now]=0;

			clo[now]=cnt2;//强联通分量编号

			siz[cnt2]++;//强联通分量节点个数

		}

	}

}

int in[maxn];

int u[maxn];

int b[maxn];

int main(){

//	freopen("a.in","r",stdin);

	n=read();

	m=read();

	for(int i=1;i<=m;i++){

		u[i]=read();

		b[i]=read();

//		cout<<u[i]<<" "<<b[i]<<endl;

		add(u[i],b[i]);

	}

	for(int i=1;i<=n;i++){

		if(!dfn[i]){

			tarjan(i);

		}

	}

	cnt=0;

	memset(head,0,sizeof(head));

	memset(e,0,sizeof(e));

	for(int i=1;i<=m;i++){

		if(clo[u[i]]!=clo[b[i]]){

			add(clo[u[i]],clo[b[i]]);

	//		cout<<clo[u[i]]<<" "<<u[i]<<" ";

	//		cout<<clo[b[i]]<<" "<<b[i]<<endl;

			in[clo[b[i]]]++;

		}

	}

	int fla=0;

	double ans=0;

//	cout<<cnt2;

	for(int i=1;i<=cnt2;i++){

		if(siz[i]==1&&!in[i]&&!fla){

			int pd=0;

//			cout<<i;

			for(int j=head[i];j;j=e[j].nex){

				int y=e[j].to;

				if(in[y]==1){

			//		cout<<y<<endl;

					pd=1;

				//	break;

				}

			}

			if(!pd)

				fla=1;

		}

		if(!in[i]){

			ans++;

		}

	}

	if(fla)

		ans--;

//	cout<<ans;

	printf("%.6f",1.0-ans/(double)n);

	return 0;

}