bzoj 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

Time Limit: 5 Sec Memory Limit: 64 MB

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.

解：强联通分量；

tarjan缩点；

then：记忆化搜索，sovle函数；

注意：first数组清零；（！！！）

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
const int N=100010;
struct node
{
    int from,to,next;
}e[N];
int first[N],book[N];
int dfn[N],low[N],stack[N],cd[N],color[N],size[N];
int tot=0,top=0,num=0;
int cnt=0;
void insert(int v,int u)
{
    e[++cnt].to=u;e[cnt].from=v;e[cnt].next=first[v];first[v]=cnt;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++tot;
    book[x]=1,stack[++top]=x;
    for(int i=first[x];i;i=e[i].next)
    {
        if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
        else if(book[e[i].to]) low[x]=min(low[x],low[e[i].to]);
    }
    if(dfn[x]==low[x])
    {
        ++num;
        while(stack[top]!=x)
        {
            book[stack[top]]=0;
            color[stack[top]]=num;
            size[num]++;
            top--;
        }
        book[x]=0;color[x]=num;size[num]++;top--;
    }
}
int ans[N];
int sovle(int x)
{
    if(ans[x]) return ans[x]; 
    ans[x]=size[x];
    if(e[first[x]].to) ans[x]+=sovle(e[first[x]].to);
    return ans[x];
}
int main()
{
    int n;
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++) scanf("%d",&x),insert(i,x);
    
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    cnt=0;
    memset(first,0,sizeof(first));
    for(int i=1;i<=n;i++)
    {
        if(color[e[i].from]!=color[e[i].to]) cd[color[e[i].from]]++,insert(color[e[i].from],color[e[i].to]);
    }
    for(int i=1;i<=n;i++)
        printf("%d
",sovle(color[i]));
    return 0;
}

bzoj 1589

=====