題目鏈接

Solution

可以考慮到如果知道環(huán)內(nèi)一點(diǎn)的身份,如果兇手在其中就查出來了,同時(shí)不會(huì)有危險(xiǎn).
那么對(duì)警察造成威脅的就是那些身份不明且不能從其他點(diǎn)轉(zhuǎn)移過來的點(diǎn).
那么大部答案就是縮完點(diǎn)之后入度為 \(0\) 的聯(lián)通塊數(shù)量.
但是,會(huì)有特殊情況:

如圖,我們就只要查 \(2\) 或者 \(1\) 其中的一點(diǎn)即可.
也就是說如果一個(gè)聯(lián)通塊僅包含一個(gè)點(diǎn),且其出邊所到的點(diǎn)都能由其他點(diǎn)推導(dǎo)出來.
那么我們可以通過調(diào)整對(duì)于入度為 \(0\) 的點(diǎn)的訪問順序以忽略這個(gè)點(diǎn).
同時(shí)這樣的點(diǎn)只能有一個(gè)(可以很簡(jiǎn)單舉出反例).

Code

#include<bits/stdc++.h> using namespace std; const int maxn=1000008; struct sj{int to,next;}a[maxn]; int head[maxn],size,flagg; int dfn[maxn],low[maxn]; int sta[maxn],top,belong[maxn]; int cnt,tot,v[maxn],n; int du[maxn],ans,num,m; int fr[maxn],to[maxn],siz[maxn]; void add(int x,int y) {a[++size].to=y;a[size].next=head[x];head[x]=size; }void tarjan(int x) {dfn[x]=low[x]=++tot;sta[++top]=x;v[x]=1;for(int i=head[x];i;i=a[i].next){int tt=a[i].to;if(!dfn[tt]){tarjan(tt);low[x]=min(low[x],low[tt]);}else if(v[tt]) low[x]=min(low[x],dfn[tt]);}if(dfn[x]==low[x]){belong[x]=++cnt;v[x]=0;do{siz[cnt]++;belong[sta[top]]=cnt;v[sta[top]]=0;}while(sta[top--]!=x);} }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y; scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int x=1;x<=n;x++)for(int i=head[x];i;i=a[i].next){int tt=a[i].to;if(belong[tt]!=belong[x])du[belong[tt]]++,fr[++num]=belong[x],to[num]=belong[tt];}memset(a,0,sizeof(a));memset(head,0,sizeof(head));size=0;for(int i=1;i<=num;i++)add(fr[i],to[i]);for(int x=1;x<=cnt;x++)if(du[x]==0){ans++;if(siz[x]==1){int flag=1;for(int i=head[x];i;i=a[i].next){int tt=a[i].to;if(du[tt]==1){flag=0;break;}}if(!flagg)flagg=flag;if(!head[x])flagg=1;}}ans-=flagg;if(n==1)ans=0;if(m==0)ans=n-1;printf("%.6lf\n",(n*1.0-ans*1.0)/(n*1.0)); }

轉(zhuǎn)載于:https://www.cnblogs.com/Kv-Stalin/p/9605664.html

總結(jié)

以上是生活随笔為你收集整理的[中山市选]杀人游戏 (Tarjan缩点)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。