食物链

本文最后更新于：2024年3月18日 晚上

食物链

问题描述

13153
  • 如图所示为某生态系统的食物网示意图，现在给你 n 个物种和 m 条能量流动关系，求其中的食物链条数。
  • 物种的名称为从 1 到 n 编号，M 条能量流动关系形如。
1
2
3
4
5
6
a1 b1
a2 b2
a3 b3
......
am-1 bm-1
am bm
  • 其中 ai bi 表示能量从物种 ai 流向物种 bi，注意单独的一种孤立生物不算一条食物链。

代码实现

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
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        // 动态规划数组，表示该节点有多少条子路径。
        int[] dp = new int[n + 1];
        // 入度数组。
        int[] in = new int[n + 1];
        ArrayList<ArrayList<Integer>> nums = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            dp[i] = -1;
            in[i] = 0;
            nums.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            nums.get(x).add(y);
            in[y]++;
        }
        int ans = 0;
        // 遍历入度为0的根结点。
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                ans += dfs(i, true, dp, nums);
            }
        }
        System.out.println(ans);
    }

    public static int dfs(int id, boolean checkSingle, int[] dp, ArrayList<ArrayList<Integer>> nums) {
        if (dp[id] != -1) {
            return dp[id];
        }
        if (nums.get(id).size() == 0) {
            // 如果为孤立节点则返回0
            if (checkSingle) {
                return 0;
            } else {
                return 1;
            }
        }
        int count = 0;
        for (int i = 0; i < nums.get(id).size(); i++) {
            count += dfs(nums.get(id).get(i), false, dp, nums);
        }
        dp[id] = count;
        return count;
    }

}