E. Trick or Treat on the Farm 采集糖果

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

1
2
2
3

#include<stdio.h>
#include<stack>
 
namespace bikuhiku {
    template <typename _T> _T gtr(_T &_compare_x,_T &_compare_y) {
        return _compare_x > _compare_y ? _compare_x : _compare_y;
    }
    template <typename _T> _T les(_T &_compare_x,_T &_compare_y) {
        return _compare_x < _compare_y ? _compare_x : _compare_y;
    }
    template <typename _T> void get_int(_T &_data_x) {
        int _signal = 1;
        char _get_c;
        _data_x = 0;
        for(_get_c = getchar();_get_c < '0'||_get_c > '9';_get_c = getchar()) if(_get_c == '-') _signal = -1;
        for(;_get_c >= '0'&&_get_c <= '9';_get_c = getchar()) _data_x = (_data_x<<3)+(_data_x<<1)+(_get_c^48);
        _data_x *= _signal;
        return;
    }
    template <typename _T> void put_int(_T _data_x) {
        if(_data_x > 9) put_int(_data_x/10);
        putchar((_data_x%10)^48);
        return;
    }
    const int _ = 0;
}//定义一块命名空间；
using namespace bikuhiku;
using namespace std;

const int z = 524288-16384-8192+512;
int n, e, ans;
 
struct line{
    int t, next;
} edge[z], side[z];
int cnt, head[z];
inline void adedge(int &f,int &t) {
    edge[++cnt].next = head[f];
    edge[cnt].t = t;
    head[f] = cnt;
    return;
}
int tot, front[z];
inline void adside(int &f,int &t) {
	side[++tot].next = front[f];
	side[tot].t = t;
	front[f] = tot;
	return;
}

int val[z];
 
stack<int> stk;
int dfn[z], low[z], time;
int belong[z];
bool instk[z];
inline void tarjan(int &u) {
    dfn[u] = low[u] = ++time;
    stk.push(u);
    instk[u] = true;
    for(register int i = head[u];i;i = edge[i].next) {
        if(!dfn[edge[i].t]) {//是树枝边；
            tarjan(edge[i].t);
            low[u] = les(low[u],low[edge[i].t]);
        } else if(instk[edge[i].t]) {//是返祖边；
            low[u] = les(low[u],dfn[edge[i].t]);
        }
    }
    if(low[u] == dfn[u]) {//构成强连通分量；
        int tmp;
        ++belong[0];
        do {
            tmp = stk.top();
            stk.pop();
            instk[tmp] = false;
            belong[tmp] = belong[0];
            ++val[belong[0]];
        } while(tmp != u);
    }
    return;
}

int note[z], cty;
int candy[z];
bool vis[z];
inline void dfs(int &u,int cdy) {
	if(!vis[u]) note[++cty] = u, vis[u] = true;
	else {//当此点未被访问；
		cdy += candy[u];
		for(int i = 1;i <= cty;++i) 
			candy[note[i]] = gtr(candy[note[i]],cdy);
		return;
	}//最重要的一步，直接将6000ms降到122ms；
	cdy += val[u];
	if(!front[u])//在终点将值赋给数组；
		for(int i = 1;i <= cty;++i) 
			candy[note[i]] = gtr(candy[note[i]],cdy);
	else
		for(register int i = front[u];i;i = side[i].next) 
			dfs(side[i].t,cdy);
	return;
}

void init() {
	get_int(n);
	for(register int i = 1;i <= n;++i) {
		get_int(e);
		adedge(i,e);
	}
	return;
}

int main() {
	init();
	for(register int i = 1;i <= n;++i)
		if(!dfn[i]) tarjan(i);
	for(register int u = 1;u <= n;++u) 
		for(register int i = head[u];i;i = edge[i].next) 
			if(belong[u] != belong[edge[i].t]) 
				adside(belong[u],belong[edge[i].t]);
	for(register int i = 1;i <= belong[0];++i) {
		if(!candy[i]) dfs(i,0);
		cty = 0;
	}
	for(register int i = 1;i <= n;++i) {
		put_int(candy[belong[i]]);
		putchar(10);
	}
    return 0^_^0;
}