BZOJ 4562: [Haoi2016]食物链

Description

如图所示为某生态系统的食物网示意图,据图回答第1小题
《BZOJ 4562: [Haoi2016]食物链》
1.数一数,在这个食物网中有几条食物链( )

 

现在给你n个物种和m条能量流动关系,求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
……
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

Input

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。
(数据保证输入数据符号生物学特点,且不会有重复的能量流动关系出现)

1<=N<=100000 0<=m<=200000
题目保证答案不会爆 int

Output

一个整数即食物网中的食物链条数

Sample Input

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

#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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据