记录编号	407154	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2017-05-20 17:48:19	内存使用	1.42 MiB

# include <bits/stdc++.h>
# define MAXN 100001 
# define getchar readc
using namespace std;

char buf[1<<18], *fs, *ft;
inline char readc() {
	return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1<<18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int gn() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

struct edge {
	int to;
	edge *ne;
	inline edge() {
		to = 0;
		ne = NULL;
	}
	inline edge(int to_, edge *ne_) {
		to = to_, ne = ne_;
	}
}*head[MAXN];

inline void addedge(int fr, int to) {
	edge *e = new edge(to, head[fr]);
	head[fr] = e;
}

int dp[MAXN], n, m;
bool has_fr[MAXN];

int dfs(int x) {
	if(!head[x]) return dp[x] = 1;
	for(edge *e = head[x]; e; e = e->ne) {
		if(dp[e->to]) {
			dp[x] += dp[e->to];
			continue;
		}
		else dp[x] += dfs(e->to);
	}
	return dp[x];
}

int main() {
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	n = gn();
	m = gn();
	for(int u, v, i = 1; i <= m; i++) {
		u = gn();
		v = gn();
		addedge(u, v);
		has_fr[v] = 1;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(head[i] && !has_fr[i]) 
		ans += dfs(i);
	}
	printf("%d\n", ans);
}