比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
食物链 |
最终得分 |
100 |
用户昵称 |
kZime |
运行时间 |
0.095 s |
代码语言 |
C++ |
内存使用 |
1.42 MiB |
提交时间 |
2017-05-20 18:01:32 |
显示代码纯文本
# 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);
}