[HAOI 2016]食物链

2022-06-06 01:00:37

Description

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

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条能量流动关系。

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

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

Hint

【样例解释】

就是上面题目描述1的那个图

各个物种的编号依次为

草 1兔 2狐 3鼠 4猫头鹰 5吃虫的鸟 6蜘蛛 7蛇 8青蛙 9食草昆虫 10

数据范围

1<=N<=100000 0<=m<=200000

题目保证答案不会爆int

题解

冠冕堂皇地出了一道$topsort$裸题...

我们为了方便统计答案将所有出度为$0$的点连向一个超级汇点。

然后按拓扑序进行$DP$，若边$u->v$将$ans[v] += ans[u]$。

另外特别注意单独的一个点不能组成食物链,所以对于入度和出度都是$0$的点我们不予考虑。

 //It is made by Awson on 2017.10.1

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = ;

 const int M = ;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 int n, m, u, v;

 struct tt {

     int to, next;

 }edge[M+N+];

 int path[N+], top;

 int in[N+], out[N+];

 int ans[N+];

 void add(int u, int v) {

     edge[++top].to = v;

     edge[top].next = path[u];

     path[u] = top;

 }

 void topsort() {

     queue<int>Q;

     while (!Q.empty()) Q.pop();

     for (int i = ; i <= n; i++)

         if (!in[i]&&out[i]) {

             Q.push(i);

             ans[i] = ;

         }

     while (!Q.empty()) {

         int u = Q.front(); Q.pop();

         for (int i = path[u]; i; i = edge[i].next) {

             int v = edge[i].to;

             in[v]--, ans[v] += ans[u];

             if (!in[v]) Q.push(v);

         }

     }

 }

 void work() {

     read(n), read(m);

     for (int i = ; i <= m; i++) {

         read(u), read(v);

         add(u, v);

         in[v]++, out[u]--;

     }

     for (int i = ; i <= n; i++)

         if (!out[i]&&in[i]) add(i, n+);

     topsort();

     printf("%d\n", ans[n+]);

 }

 int main() {

     work();

     return ;

 }

码农公寓