這個題很容易想到正解就是縮點找入度為零的點，那么我們考慮一種特殊情況就是，一個入度為零的點我們不訪問他就知道他是不是兇手，那么這樣的話就是：I. 他是一個真·孤立的點 II. 他在圖里但是在他的強聯通分量里只有他一個而且他能到達的所有點都能被其他入度為零的點所達到 ，這個細節70分.......

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #define N 100010 #define M 300010 using namespace std; inline int read() {int sum=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}return sum; } struct VIA {int to,next; }c[M]; struct Via {int to,next,w; }C[M<<1]; int head[N],t,Head[N],T; int dfn[N],low[N],stack[N],top; inline void add(int x,int y) {c[++t].to=y;c[t].next=head[x];head[x]=t; } inline void Add(int x,int y,int z) {C[++T].to=y;C[T].w=z;C[T].next=Head[x];Head[x]=T; } inline int Min(int x,int y) {return x<y?x:y; } int n,m,Ti,num,belong[N]; bool in[N]; bool special[N]; void Tarjan(int x) {in[x]=1;stack[++top]=x;dfn[x]=low[x]=++Ti;for(int i=head[x];i;i=c[i].next)if(!dfn[c[i].to]){Tarjan(c[i].to);low[x]=Min(low[x],low[c[i].to]);}else if(in[c[i].to])low[x]=Min(low[x],dfn[c[i].to]);if(low[x]==dfn[x]){int j,i=0;++num;do{j=stack[top--];in[j]=0;belong[j]=num;i++;}while(j!=x);if(i==1)special[num]=1;} } int In[N]; inline void Build_New() {for(int x=1;x<=n;x++)for(int i=head[x];i;i=c[i].next)if(belong[x]!=belong[c[i].to])++In[belong[c[i].to]],Add(belong[x],belong[c[i].to],1),Add(belong[c[i].to],belong[x],-1); } inline void Init() {n=read(),m=read();for(int i=1,x,y;i<=m;i++)x=read(),y=read(),add(x,y); } int visit[N]; bool F(int x,int to) {if(visit[x]==t)return 0;if(In[x]==0&&x!=to)return 1;for(int i=Head[x];i;i=C[i].next)if(C[i].w==-1)if(F(C[i].to,to))return 1;return 0; } inline int find() {t=0;for(int i=1;i<=num;i++)if(In[i]==0&&special[i]){if(Head[i]==0)return 1;bool ans=1;for(int j=Head[i];j;j=C[j].next)if(C[j].w==1){++t;ans&=F(C[j].to,i);}if(ans)return 1;}return 0; } inline void work() {for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);Build_New();int get=0;for(int i=1;i<=num;i++)if(!In[i])get++;get=n-get;get+=find();double ans=(double)get/n;printf("%.6lf",ans); } int main() {Init();work();return 0; }

?

.

轉載于:https://www.cnblogs.com/TSHugh/p/7248192.html

總結

以上是生活随笔為你收集整理的[BZOJ 2438] [中山市选2011]杀人游戏 Tarjan缩点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。