P4819 [中山市选]杀人游戏 Tarjan

题意：

有(N)个人，他们通过(M)条单向的认识关系形成了一张图，其中有一个人是杀手，若遇到杀手则你会死亡，若遇到平民，ta会告诉你，ta认识的人中每个人的身份，求保证自身安全的情况下查到杀手的概率最大是多少？

范围&性质：(1le Nle 10^5,qle Mle 3 imes 10^5)

分析：

什么情况下会遇到杀手，那就是查一个不清楚身份的人时（好像是一句废话）

所以只需要查找所有入度为0的点就可以了，但本题点数过大，直接(O(n^2))会被卡，那么我们考虑怎么优化，我们发现对于一个强联通分量，里面的点都是互相认识的，所以我们先缩点，对于入度为0的强连通分量查询

tips：在实际情况中还可以利用排除法，所以当一个入度为0且大小为1的点，他的所有儿子入度都大于1，那么意味着这个点可以不用查，因为最后我们可以通过排除法确定他的身份

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	const int maxn = 1e5+5;
	int n,m,cnt=0,top=0,scc=0,ans=0,tim=0;
	int head[maxn],u[maxn],v[maxn],rd[maxn],cd[maxn],st[maxn];
	int dfn[maxn],low[maxn],belong[maxn],pre[maxn];
	bool ins[maxn],flag;
	
	vector<int> to[maxn];
	map<int,bool> edge[maxn];
	
	struct Edge
	{
		int to,nxt;
	}e[maxn<<2];
	
	void add(int u,int v)
	{
		e[++cnt].to=v;
		e[cnt].nxt=head[u];
		head[u]=cnt;
	}
	
	void tarjan(int u)
	{
		dfn[u]=low[u]=++tim;
		st[++top]=u;
		ins[u]=true;
		for(int i=0;i<to[u].size();i++)
		{
			int v=to[u][i];
			if(!dfn[v])
			{
				tarjan(v);
				low[u]=min(low[u],low[v]);
			}
			else if(ins[v]) low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u])
		{
			scc++;
			do
			{
				int v=st[top];
				ins[v]=false;
				belong[v]=scc;
			}
			while(st[top--]!=u);
		}
	}
	
	void work()
	{
		int a,b;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			to[a].push_back(b);
		}
		for(int i=1;i<=n;i++)
		{
			if(!dfn[i]) tarjan(i);
		}
		
		for(int u=1;u<=n;u++)
		{
			for(int i=0;i<to[u].size();i++)
			{
				int v=to[u][i];
				if(belong[u]!=belong[v]&&!edge[belong[u]][belong[v]])
				{
					add(belong[u],belong[v]);
					edge[belong[u]][belong[v]]=true;
					rd[belong[v]]++;
					cd[belong[u]]++;
				}
			}
			pre[belong[u]]++;
		}
		for(int i=1;i<=scc;i++)
		{
			if(rd[i]==0)
			{
				ans++;
				if(pre[i]==1)
				{
					if(cd[i]==0) flag=true;
					else
					{
						bool ok=false;
						for(int j=head[i];j;j=e[j].nxt)
						{
							int v=e[j].to;
							if(rd[v]<=1)
							{
								ok=true;
								break;
							}
						}
						if(!ok) flag=true;
					}
				}
			}
		}
		if(flag) ans--;
		printf("%.6lf
",1.0-(double)ans/(double)n);
	}
	
} 

int main()
{
	zzc::work();
	return 0;
}