自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻_ AFO

搬运于2025-08-24 21:46:13，当前版本为作者最后更新于2019-11-06 19:22:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好多大佬用记搜， emm， 其实……

直接裸toposort加个f统计方案就好啦

考虑到拓扑排序的先后次序问题, 在更新入度的时候顺便将方案数进行累加

最后答案就是 $\sum$ 无出边的点

注意单个点不算方案

生命苦短， 直接上代码

#include <iostream>
#include <vector>
#include <queue>
#define ORZ main
using namespace std;
const int N=1008611;
int n, m, f[N], rd[N];
vector <int> e[N];

inline int JI_DE_DIAN_GE_ZAN()
{
	queue <int> q;
	int ans=0;
	for(int i=1; i<=n; i++)
	if(!rd[i] && e[i].size()) // 单个点不算方案
		q.push(i), f[i]=1; 
	
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		if(!e[x].size()) ans+=f[x];
		for(auto t : e[x])
		{
			f[t]+=f[x], rd[t]--; // f来统计方案
			if(!rd[t]) q.push(t);
		}
	}
	return ans;
} // 裸的

int ORZ ()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1, x, y; i<=m; i++)
	{
		cin>>x>>y; rd[y]++;
		e[x].push_back(y);
	}
	cout<<JI_DE_DIAN_GE_ZAN();
	return ~~ (0 ^ 0);
}