BZOJ1589[Usaco2008Dec]TrickorTreatontheFarm采集糖果tarjan+拓扑

Description

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果．农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果．第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．

Input

第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．

Output

共N行，一行一个整数表示一只奶牛可以采集的糖果数量．

Sample Input

4 //有四个点
 1 //1有一条边指向1
 3 //2有一条边指向3
 2 //3有一条边指向2
 3

INPUT DETAILS:

Four stalls.
* Stall 1 directs the cow back to stall 1.
* Stall 2 directs the cow to stall 3
* Stall 3 directs the cow to stall 2
* Stall 4 directs the cow to stall 3

Sample Output

1
2
2
3

HINT

Cow 1: Start at 1, next is 1. Total stalls visited: 1. Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. 
Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. 
Total stalls visited: 3.

​​传送门​​

很容易想到，当一个奶牛不断地走，走过的地方再走没有用，

那么它最终会无路可走，或者陷入一个环内。

我们只要强联通分量缩点，然后就能得到一个DAG；

在这个DAG上，把边反向之后每次找入度为零的点统计答案（拓扑）

也就是说，一个点，它本来可以走若干步，最终无路可走或者陷入环内；

缩点之后变成了DAG，每个点记录一下这个环的size，

则陷入环内的情况也变成了无路可走。

那么有种暴力的想法就是一个点u开始不停走直到不能走，

路径经过的所有点的size之和就是这个点的答案。

不过一条链，很显然超时……

改进方法也不难，只要按照拓扑序来就好了，每次找入度为0的点，

假设这个点的答案是f[x]，则所有x->y，f[y]+=f[x]

f[i]=sz[i] //初始

不是很难，也没什么细节……

#include<bits/stdc++.h>
using namespace std;
const int 
  N=100005;
int n,Time,Ecnt,top,sccnum;
int stk[N],Next[N],into[N];
int DFN[N],LOW[N],scc[N],sz[N],f[N];
bool instack[N];
queue<int>Q;
struct Edge{
  int next,to;
}E[N];int head[N];
void add(int u,int v){
  E[++Ecnt].next=head[u];
  E[Ecnt].to=v;
  head[u]=Ecnt;
}
void tarjan(int u){
  DFN[u]=LOW[u]=++Time;
  instack[u]=1,stk[++top]=u;
  for (int i=head[u];i;i=E[i].next){
    int v=E[i].to;
    if (!DFN[v]){
      tarjan(v);
      LOW[u]=min(LOW[u],LOW[v]);
    } else
    if (instack[v]) LOW[u]=min(LOW[u],DFN[v]);
  }
  if (DFN[u]==LOW[u]){
    sz[++sccnum]=1;
    while (stk[top]!=u){
      instack[stk[top]]=0;
      scc[stk[top--]]=sccnum;
      sz[sccnum]++;
    }
    instack[stk[top]]=0;
    scc[stk[top--]]=sccnum;
  }
}
void rebuild(){
  Time=top=0;
  for (int i=1;i<=n;i++)
    if (!DFN[i]) tarjan(i);
  Ecnt=0;
  memset(head,0,sizeof(head));
  for (int i=1;i<=n;i++)
    if (scc[i]!=scc[Next[i]])
      add(scc[Next[i]],scc[i]),into[scc[i]]++;
  for (int i=1;i<=sccnum;i++) f[i]=sz[i];
}
void solve(){
  while (!Q.empty()) Q.pop();
  for (int i=1;i<=sccnum;i++)
    if (!into[i]) Q.push(i);
  while (!Q.empty()){
    int u=Q.front();Q.pop();
    for (int i=head[u];i;i=E[i].next){
      int v=E[i].to;
      into[v]--,f[v]+=f[u];
      if (!into[v]) Q.push(v);
    }
  }
}
int main(){
  scanf("%d",&n),Ecnt=0;
  for (int i=1;i<=n;i++){
    scanf("%d",&Next[i]);
    if (i!=Next[i]) add(i,Next[i]);
  }
  rebuild();
  solve();
  for (int i=1;i<=n;i++)
    printf("%d\n",f[scc[i]]);
  return 0;
}