记录编号	253992	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	C++	运行时间	0.351 s
提交时间	2016-04-24 13:07:07	内存使用	2.38 MiB

#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int readint()
{
	int x = 0, c;
	while (!isdigit(c = getchar()));
	do
		x = x * 10 + c - '0';
	while (isdigit(c = getchar()));
	return x;
}
int n, m;
int in[100010], out[100010];
vector<int> edge[100010];
queue<int> q;
long long cnt[100010];
int main()
{
	freopen("chain_2016.in", "r", stdin);
	freopen("chain_2016.out", "w", stdout);
	n = readint();
	m = readint();
	for (int i = 1; i <= n; i++)
		edge[i].clear();
	for (int i = 0; i < m; i++)
	{
		int a = readint();
		int b = readint();
		edge[a].push_back(b);
		out[a]++;
		in[b]++;
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!in[i])
		{
			cnt[i] = 1;
			q.push(i);
			if (!out[i])
				ans--;
		}
	}
	while (!q.empty())
	{
		int ls = q.front();
		q.pop();
		for (int i = 0; i < (int)edge[ls].size(); i++)
		{
			cnt[edge[ls][i]] += cnt[ls];
			in[edge[ls][i]]--;
			if (!in[edge[ls][i]])
			{
				q.push(edge[ls][i]);
			}
		}
	}
	for (int i = 1; i <= n; i++)
		if (!out[i])
			ans += cnt[i];
	printf("%d\n", ans);
	return 0;
}