题意：每一只奶牛都从一个棚栏出发，如果走到一个地方，该地方走过的话，就停止，请问每一只奶牛最多可以走过都是个棚栏。
思路，先找出该有向图中所有的环，然后对每一个环进行缩点，计算每一个环的大小，如果走到一个环中的任意一个点后，一定会出现重复走到一个点，所以就加上这个额环的大小，然后停止，因为要计算所有点可以走到最远的距离，所以可以记忆化搜索的方式进行优化。`
#include <cstdio> #include <cmath> #include <stack> #include <queue> #include <string> #include <iostream> #include <sstream> #include <ostream> #include <cstring> #include <vector> #include <cstdlib> #include <algorithm> #include <map> #include<iomanip> #include <set> #include <bitset> #define INT_MINs -2000000000 #define INT_MAXs 1000000001 #define mod 1000000007 #define MID mid=(l+r)/2 #define REP1(i,x,y) for(int i=x;i<y;i++) #define REP2(i,x,y) for(int i=x;i<=y;i++) #define ls (2*k) #define lr (2*k+1) #define lson l,mid,2*k #define lron mid+1,r,2*k+1 #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define IOS ios::sync_with_stdio(0); #define pb(a) push_back(a) #define pi acos(-1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int dx[8] = { 0,-1,0,1,-1,-1,1,1}, dy[8] = { 1,0,-1,0,-1,1,-1,1}; int n,top,dfn[100005],st[100005],vis[100005],low[100005],cnt,head[200005],t; int num,fa[100005],sum[100005],ans[100005],num2[100005]; struct node{ int u,v,next; }e[200005]; void addedge(int u,int v) { e[++cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void tarjan(int x)//tarjan缩点模板 { low[x]=dfn[x]=++num; st[++top]=x; vis[x]=1; for(int i=head[x];i;i=e[i].next) { int v=e[i].v; if(!vis[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(dfn[v]) { low[x]=min(low[x],low[v]); } } if(low[x]==dfn[x]) { int k; do { k=st[top--]; fa[k]=x; if(k==x) { break; } sum[x]++; }while(k!=x); } } int dfs(int x,int last) { if(num2[x])//记忆化搜索 return num2[x]; int anss=0; anss+=sum[fa[x]]; if(sum[fa[x]]>1)//为一个环 return anss; for(int i=head[x];i;i=e[i].next) { int v=e[i].v; if(v==x)//特判u走到u的情况 break; if(v!=last) { anss+=dfs(v,x); } } num2[x]=anss; return anss; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { int v; cin>>v; addedge(i,v); } for(int i=1;i<=n;i++) fa[i]=i,sum[i]=1;//初始化 for(int i=1;i<=n;i++) { if(!vis[i]) { tarjan(i); } } for(int i=1;i<=n;i++) { ans[i]+=dfs(i,0); } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }