P4017. 最大食物链计数

发表于 分类于 阅读次数： Waline： 本文字数： 219 阅读时长 ≈ 1 分钟

考点

  • 拓扑排序

题解

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
#include <bits/stdc++.h>
using namespace std;
const int LEN = 5e5 + 50, MOD = 80112002;
int n, m, f[LEN], ind[LEN], outd[LEN];
queue<int> q;
vector<int> e[LEN];

void toposort() {
  for (int i = 1; i <= n; ++i)
    if (ind[i] == 0) {
      //将入度为0的点加入队列
      q.emplace(i);
      f[i] = 1;
    }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < e[x].size(); ++i) {
      int y = e[x][i];
      f[y] = (f[y] + f[x]) % MOD;
      //点y无入度，将点y加入队列
      if (--ind[y] == 0) q.emplace(y);
    }
  }
}

int main() {
  int x, y;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> x >> y;
    //邻接表存储边
    e[x].emplace_back(y);
    //点x的出度加1，点y的入度加1
    ++outd[x], ++ind[y];
  }
  toposort();
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    //在出度为0的点中统计答案
    if (outd[i] == 0) ans = (ans + f[i]) % MOD;
  }
  cout << ans;
  return 0;
}

思路

拓扑排序的模板题，直接用《深基》的截图吧~