题目链接
题意：给定一个图，每个节点的出度为1，求最小环的结点数
参考：http://www.cnblogs.com/83131yyl/p/5020528.html
可以先把不在环内的点清除掉，再对于每个环跑一遍长度
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define maxn 200010 6 int in_degree[maxn],reach[maxn]; 7 bool vis[maxn]; 8 int n,ans; 9 int read(){ 10 int x=0,f=1; 11 char ch=getchar(); 12 while (ch<'0'||ch>'9'){ 13 if (ch=='-') f=-1; 14 ch=getchar(); 15 } 16 while (ch>='0'&&ch<='9'){ 17 x=x*10+ch-'0'; 18 ch=getchar(); 19 } 20 return x*f; 21 } 22 void Clean(int i){//清除不在环内的结点 23 vis[i]=1; 24 in_degree[reach[i]]--; 25 if (!in_degree[reach[i]]) Clean(reach[i]); 26 } 27 void dfs(int p,int len){//求环的长度 28 vis[p]=1; 29 if (!vis[reach[p]]) dfs(reach[p],len+1); 30 else if (len!=1) ans=min(ans,len); 31 } 32 int main(){ 33 n=read(); 34 memset(reach,0,sizeof(reach)); 35 memset(in_degree,0,sizeof(in_degree)); 36 memset(vis,0,sizeof(vis)); 37 for (int i=1;i<=n;i++){ 38 reach[i]=read(); 39 in_degree[reach[i]]++; 40 } 41 for (int i=1;i<=n;i++) 42 if (!in_degree[i]&&!vis[i]) Clean(i);//注意两个限制条件，防止重复的删除 43 ans=n+1; 44 for (int i=1;i<=n;i++) 45 if (!vis[i]) dfs(i,1); 46 ans=ans>n?0:ans; 47 printf("%d\n",ans); 48 return 0; 49 }
另外常规的解法是用tarjan求强连通分量 留坑