Description
如图所示为某生态系统的食物网示意图，据图回答第1小题
1.数一数，在这个食物网中有几条食物链（ ）
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
……
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。
（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）
1<=N<=100000 0<=m<=200000
题目保证答案不会爆 int
Output
一个整数即食物网中的食物链条数
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9
Sample Output
9
Solution
dp[i]表示到i这种生物一共有几条食物链。
dp[i]是所有边(u->i)的dp[u]之和。
推这个dp我们用拓扑序就好了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
struct edge_type {
int to, next;
} edge[500005];
int h[100005], cnte = 1;
int cd[100005], rd[100005], sta[100005], tail = 0;
int n, dp[100005];
void ins(int x, int y) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
h[x] = cnte;
}
int ans = 0;
void DP() {
for (int i = 1; i <= n; ++i) {
if (rd[i] == 0 && cd[i] != 0) {
dp[i] = 1;
sta[++tail] = i;
}
}
int now;
while (tail) {
now = sta[tail--];
for (int i = h[now]; i; i = edge[i].next) {
dp[edge[i].to] += dp[now];
--rd[edge[i].to];
if (!rd[edge[i].to]) {
sta[++tail] = edge[i].to;
}
}
}
for (int i = 1; i <= n; ++i)
if (!cd[i])
ans += dp[i];
}
int main() {
n = getint(); int m = getint();
int x, y;
while (m --) {
y = getint(); x = getint();
ins(x, y);
cd[x]++; rd[y]++;
}
DP();
printf("%d", ans);
return 0;
}
|