题意：
n个节点，每个节点有一个后继节点，问从每个节点出发能到多少个没去过的节点。n≤100000。
题解：
因为每个节点只有一个后继节点，所有tarjan缩点后就会变成一堆链，对每条链dfs一下即可。
代码：
1 #include2 #include 3 #include 4 #include 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 #define ll long long 8 using namespace std; 9 10 inline int read(){11 char ch=getchar(); int f=1,x=0;12 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();}13 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14 return f*x;15 }16 struct e{ int f,t,n;}es[maxn]; int g[maxn],ess,n;17 void pe(int f,int t){es[++ess]=(e){f,t,g[f]}; g[f]=ess;}18 bool vis[maxn]; int bel[maxn],sm[maxn],tim,pre[maxn],low[maxn],tot,ins[maxn]; stack st;19 void dfs1(int x){20 vis[x]=ins[x]=1; st.push(x); low[x]=pre[x]=++tim;21 for(int i=g[x];i;i=es[i].n)22 if(!vis[es[i].t])dfs1(es[i].t),low[x]=min(low[x],low[es[i].t]);23 else if(ins[es[i].t])low[x]=min(low[x],pre[es[i].t]);24 if(low[x]==pre[x]){25 tot++;26 while(!st.empty()){27 int now=st.top(); st.pop(); bel[now]=tot; sm[tot]++; ins[now]=0; if(now==x)break;28 }29 }30 }31 void dfs2(int x){32 for(int i=g[x];i;i=es[i].n){33 if(!vis[es[i].t])vis[es[i].t]=1,dfs2(es[i].t),sm[x]+=sm[es[i].t];else sm[x]+=sm[es[i].t];34 }35 }36 int main(){37 n=read(); inc(i,1,n){ int x=read(); pe(i,x);} inc(i,1,n)if(!vis[i])dfs1(i);38 int m=ess; ess=0; memset(g,0,sizeof(g));39 inc(i,1,m)if(bel[es[i].f]!=bel[es[i].t])pe(bel[es[i].f],bel[es[i].t]);40 memset(vis,0,sizeof(vis)); inc(i,1,tot)if(!vis[i])vis[i]=1,dfs2(i);41 inc(i,1,n)printf("%d\n",sm[bel[i]]); return 0;42 }
20160923