记录编号	306876	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 灾难	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.342 s
提交时间	2016-09-13 14:30:19	内存使用	4.85 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int i,n,m,k,d=0,x=0;
int f[70010],fa[70010],dfn[70010],best[70010],idom[70010],semi[70010],id[70010];
int bh[70010],z[70010],s[70010];
vector <int> l[70010],fl[70010],L[70010];

inline int read(){
	int p=0; char c=getchar();
	while (c<'0'||c>'9')	c=getchar();
	while (c>='0'&&c<='9')	p=p*10+c-48,c=getchar();
	return p;
}

inline void DFS(int x){
	int i=0;
	dfn[x]=++d;	id[d]=x;
	for (i=l[x].size()-1;i>=0;i--)
		if (!dfn[l[x][i]])	{
		DFS(l[x][i]);	fa[l[x][i]]=x;	
	}
}

inline int find(int v)
{
    if(v==f[v]) return v;
    int y=find(f[v]);
    if(dfn[semi[best[f[v]]]] < dfn[semi[best[v]]]) best[v] = best[f[v]];
    return f[v] = y;
}

void tarjan()
{
    for(int i=d,u;i>=2;--i)
    {
        u = id[i];
        for(int j=fl[u].size()-1;j>=0;j--)
        {
			if (!dfn[fl[u][j]])	continue;
			find(fl[u][j]);
			if(dfn[semi[best[fl[u][j]]]]<dfn[semi[u]]) semi[u]=semi[best[fl[u][j]]];
		}
		L[semi[u]].push_back(u);
        f[u] = fa[u];u = id[i - 1];
        for(int j=L[u].size()-1;j>=0;j--)
        {
            find(L[u][j]);
            if(semi[best[L[u][j]]] == u) idom[L[u][j]] = u;
            else idom[L[u][j]] = best[L[u][j]];
        }
    }
    for(int i = 2, u; i <= d; ++i)
    {
        u = id[i];
        if(idom[u] != semi[u]) idom[u] = idom[idom[u]];
    }
}

inline void Solve(){
	int i=0,t=1;
	for (i=1;i<=n+1;i++)	bh[idom[i]]++;
	for (i=1;i<=n+1;i++)	if (!bh[i])	z[++z[0]]=i;
	while (t<=z[0]){
		s[z[t]]++;	s[idom[z[t]]]+=s[z[t]];	bh[idom[z[t]]]--;
		if (!bh[idom[z[t]]])	z[++z[0]]=idom[z[t]];
	t++;
	}
	for (i=1;i<=n;i++)	printf("%d\n",s[i]-1);
}

inline void Work(){
	int i=0;
	for (i=1;i<=n+1;i++)	f[i]=semi[i]=best[i]=i;
	d=0;	DFS(n+1);	
	tarjan();	Solve();
}

int main(){
	freopen("catas.in","r",stdin);
	freopen("catas.out","w",stdout);
	n=read();
	for (i=1;i<=n;i++){
		k=read();	if (k==0) {
		l[n+1].push_back(i);	fl[i].push_back(n+1);
		continue;}
		while (k!=0){
			l[k].push_back(i);	fl[i].push_back(k);	k=read();}
	}
	Work();
	return 0;
}