题解 - [Luogu P3183] [HAOI2016] 食物链

发表于 更新于 分类于 ， 本文字数： 418 阅读时长 ≈ 2 分钟

题目链接

原始题面

题目描述

如图所示为某生态系统的食物网示意图，据图回答第 1 小题

现在给你 \(n\) 个物种和 \(m\) 条能量流动关系，求其中的食物链条数.

物种的名称为从 \(1\) 到 \(n\) 编号

\(m\) 条能量流动关系形如 \(a_1\to b_1, a_2\to b_2, a_3\to b_3, ..., a_{m-1}\to b_{m-1}, a_m\to b_m\) 其中 \(a_i\to b_i\) 表示能量从物种 \(a_i\) 流向物种 \(b_i\)

注意单独的一种孤立生物不算一条食物链

输入输出格式

输入格式

第一行两个整数 \(n\) 和 \(m\)

接下来 \(m\) 行，每行两个整数 \(a_i\), \(b_i\), 描述 \(m\) 条能量流动关系.

数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现

\(1\leqslant n\leqslant 100000, 0\leqslant m\leqslant 200000\)

输出格式

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

输入输出样例

输入样例 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

输出样例 #1

1
9

解题思路

很显然就是一 dfs

从入度为 \(0\) 的点开始，每一个点对应的食物链条数是所有出度的食物链条数之和，出度为 \(0\) 的点食物链条数为 \(1\)

注意所有点不一定连通 (当时漏看这个直接 20pts)

但是直接暴搜肯定不行，需要记忆化

时间复杂度

\(O(m+n)\)

代码参考

Show code

Luogu_P3183view raw
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#define _for(i, l, r) for (auto i = (l); i <= (r); ++i)
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
i64 p, p3 = -1;
i64 getc() {
  return p1 == p2 &&
             (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
           EOF :
           *p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  i64 f = 0;
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getc();
  }
  if (f) x = -x;
  read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = hh;
  print(oth...);
}
template <typename T>
void print_h(T x, char h) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = h;
}
void putchar(char a) { buf2[++p3] = a; }
}  // namespace FastIO
using FastIO::print;
using FastIO::print_h;
using FastIO::read;
const i64 M = 2e6 + 5;
const i64 N = 1e6 + 5;
i64 n, m;
struct edge {
  i64 to, next;
} e[M];
i64 head[N], cnt;
void add(i64 u, i64 v) {
  e[++cnt] = {v, head[u]};
  head[u] = cnt;
}
int in[N], out[N];
i64 f[N];
i64 dfs(i64 pos) {
  if (f[pos]) return f[pos];
  if (in[pos] && !out[pos]) return f[pos] = 1;
  for (i64 i = head[pos]; i; i = e[i].next) { f[pos] += dfs(e[i].to); }
  return f[pos];
}
int main() {
  read(n, m);
  for (i64 i = 1, x, y; i <= m; ++i) {
    read(x, y);
    add(x, y);
    ++in[y];
    ++out[x];
  }
  i64 ans = 0;
  _for(i, 1, n) {
    if (!in[i]) ans += dfs(i);
  }
  print(ans);
ex:
  FastIO::flush();
  return 0;
}