题解 P2661 【信息传递】

本蒟蒻比较奇葩，用了个tarjan求强联通分量= =，竟然过了！！ （不过其实完全可以把不是只有一个点的强联通分量当环使） 代码长度相对来说可能不是很短，其实根本没必要打tarjan 但是tarjan很无脑，嗯嗯。按着模板敲一遍就行。不喜勿喷 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,ans=1000000; int sta[200001],top=0; int dfn[200001],low[200001],tot=0; int head[200001],nxt[200001],to[200001],cnt=0; int f[200001]; void addedge(int x,int y)//邻接链表存图 { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void tarjan(int u)//tarjan求强联通分量 { f[u]=1; dfn[u]=low[u]=++tot; sta[++top]=u;//入栈 for(int i=head[u];i!=0;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(f[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { int res=0; do { f[sta[top]]=0; res++; }while(sta[top--]!=u);//出站并统计个数 if(res!=1) ans=min(ans,res);//注意，一个点不算一个环，排除掉就能过啦 } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int a; scanf("%d",&a); addedge(i,a);//加边，是有向边，别加两次 } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); cout<<ans; return 0; } ```