可达性统计

给定一个有向无环图,询问每个点可以到达点的数目.

void toposort()
{
	for(rint i=1;i<=n;i++) if(!deg[i]) q.push(i);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		f[x].set(x,1);
		for(rint i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			f[y]=f[y]|f[x];
			if(--deg[y]==0) q.push(y);
		}
	}
}


int main()
{
	n=read(); m=read();
	for(rint i=1;i<=m;i++)
	{
		int x=read(),y=read();
		deg[x]++; add(y,x);
	}
	toposort();
	for(rint i=1;i<=n;i++)
		printf("%d\n",f[i].count());
	return 0;
}

值得注意的技巧:

1. 有向无环图上的动态规划问题. 采用拓扑排序来确定dp序, 如果需要倒着来,那么就建立反图
2. 我们不知道两个点中间的可达点是否有重复的点 采用状压dp的方式来解决.