一个房间能到另一个房间,有向图,奶牛从自己编号(1到n)的点出发,如果回到以前到过的点就停止,问每头奶牛可以经过几个点;
情况分两种,
一,奶牛在环上,能走的是环的大小,二,一条链连接一个环,大小是链+环;
要预先处理自环的答案(1),还有环的大小是1的(并不在环上的点);
一开始还以为可能出现只有一条链没有环的,但是因为每个点都有一条出边,所以不必担心;
#include<cstdio> #include<cstring> #include<stack> #include<algorithm> using namespace std; const int maxn=1e5+10; int pre[maxn*2],last[maxn],other[maxn*2],l; stack<int> s; void add(int x,int y) { l++; pre[l]=last[x]; last[x]=l; other[l]=y; } int belong[maxn]; int qw; int n; int ru[maxn]; int cnt,dfn[maxn],low[maxn]; int next[maxn]; void dfs(int x) { s.push(x); dfn[x]=low[x]=++cnt; ru[x]=1; for(int p=last[x];p;p=pre[p]) { int v=other[p]; if(!dfn[v]) { dfs(v); low[x]=min(low[x],low[v]); } else if(ru[v]) { low[x]=min(low[x],dfn[v]); } } if(dfn[x]==low[x]) { belong[x]=++qw; while(!s.empty()) { int y=s.top(); s.pop(); ru[y]=0; belong[y]=qw; if(y==x) break; } } } int ring[maxn]; int ans[maxn]; void search(int x,int y,int stp) { if(ans[y]) { ans[x]=ans[y]+stp; return ; } else search(x,next[y],stp+1); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&next[i]); add(i,next[i]); if(next[i]==i) ans[i]=1; } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);//一定要注意图不一定都联通 for(int i=1;i<=n;i++) { ring[belong[i]]++;//记录环的大小 } for(int i=1;i<=n;i++) { if(ring[belong[i]]!=1) ans[i]=ring[belong[i]]; } for(int i=1;i<=n;i++) { if(!ans[i]) search(i,next[i],1); } for(int i=1;i<=n;i++) { printf("%d\n",ans[i]); } return 0; }