#include <bits/stdc++.h>
using namespace std;
int dfn[200001],low[200001],head[200001],cnt;
int ans=0x3f3f3f,temp,rank,tot,s[200001];
bool vist[200001];
inline int read()
{
int X=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){X=X*10+ch-'0';ch=getchar();}
return X;
}
struct node
{
int to,next;
}edge[20000001];
inline void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
inline void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s[++rank]=x;
vist[x]=1;
for(int i=head[x];i!=-1;i=edge[x].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else if(vist[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
temp=0;
if(low[x]==dfn[x])
do
{
temp++;
vist[s[rank]]=0;
rank--;
}while(x!=s[rank+1]);
if(temp!=1&&temp!=0)
ans=min(temp,ans);
}
int main()
{
memset(head,-1,sizeof(head));
int n=read();
for(int i=1;i<=n;i++)
{
int m=read();
addedge(i,m);
}
for(int i=0;i<n;i++)
if(!dfn[i])
tarjan(i);
printf("%d",ans);
}1.####
by sky_silence_gdk @ 2018-09-16 16:34:38
```cpp
#include <bits/stdc++.h>
using namespace std;
int dfn[200001],low[200001],head[200001],cnt;
int ans=0x3f3f3f,temp,rank,tot,s[200001];
bool vist[200001];
inline int read()
{
int X=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){X=X*10+ch-'0';ch=getchar();}
return X;
}
struct node
{
int to,next;
}edge[20000001];
inline void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
inline void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s[++rank]=x;
vist[x]=1;
for(int i=head[x];i!=-1;i=edge[x].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else if(vist[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
temp=0;
if(low[x]==dfn[x])
do
{
temp++;
vist[s[rank]]=0;
rank--;
}while(x!=s[rank+1]);
if(temp!=1&&temp!=0)
ans=min(temp,ans);
}
int main()
{
memset(head,-1,sizeof(head));
int n=read();
for(int i=1;i<=n;i++)
{
int m=read();
addedge(i,m);
}
for(int i=0;i<n;i++)
if(!dfn[i])
tarjan(i);
printf("%d",ans);
}
```
by sky_silence_gdk @ 2018-09-16 16:36:13
有没有大佬解答一下我的tarjan哪里出了问题
by sky_silence_gdk @ 2018-09-16 16:39:27
哇这题居然必须特判 temp=2直接退出
就过了%%%
by sky_silence_gdk @ 2018-09-16 17:01:54
%%%
by 信赖滴星辰 @ 2018-09-26 15:47:23