P3183 [HAOI2016]食物鏈

題目描述

如圖所示為某生態系統的食物網示意圖，據圖回答第1小題現在給你n個物種和m條能量流動關係，求其中的食物鏈條數。物種的名稱為從1到n編號M條能量流動關係形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量從物種ai流向物種bi,註意單獨的一種孤立生物不算一條食物鏈

輸入輸出格式

輸入格式：

第一行兩個整數n和m,接下來m行每行兩個整數ai bi描述m條能量流動關係。（數據保證輸入數據符號生物學特點，且不會有重覆的能量流動關係出現）1<=N<=100000 0<=m<=200000題目保證答案不會爆 int

輸出格式：

一個整數即食物網中的食物鏈條數

輸入輸出樣例

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

題目標簽寫的是動態規劃，但是自己yy了一種拓撲排序+出入度統計的做法，第一遍交居然A了，，
做法很簡單，
記兩個入度數組，一個用作拓撲排序，一個用作判斷答案，然後記一個出度，
拓撲排序
最後特判一下加個和就好

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=400001;
 8 inline void read(int &n)
 9 {
10     char c=getchar();n=0;bool flag=0;
11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 struct node
15 {
16     int u,v,w,nxt;
17 }edge[MAXN];
18 int head[MAXN];
19 int num=1;
20 int dp[MAXN];
21 int chudu[MAXN];
22 int rudu2[MAXN];
23 inline void add_edge(int x,int y,int z)
24 {
25     edge[num].u=x;
26     edge[num].v=y;
27     edge[num].w=z;
28     edge[num].nxt=head[x];
29     head[x]=num++;
30 }
31 int rudu[MAXN];
32 int n,m;
33 void Topsort()
34 {
35     queue<int>q;
36     int tot=0;
37     for(int i=1;i<=n;i++)
38         if(!rudu[i])    q.push(i),tot++;
39     while(q.size()!=0)
40     {
41         int p=q.front();
42         q.pop();
43         for(int i=head[p];i!=-1;i=edge[i].nxt)
44         {
45             dp[edge[i].v]+=dp[p];
46             rudu[edge[i].v]--;
47             if(!rudu[edge[i].v]    )    q.push(edge[i].v);
48         }
49     }
50 }
51 int main()
52 {
53     memset(head,-1,sizeof(head));
54     read(n);read(m);
55     for(int i=1;i<=m;i++)
56     {
57         int a,b;read(a);read(b);
58         add_edge(a,b,1);
59         rudu[b]++;
60         rudu2[b]++;
61         chudu[a]++;
62     }
63     for(int i=1;i<=n;i++)
64         if(!rudu[i])    dp[i]=1;
65     Topsort();
66     int ans=0;
67     for(int i=1;i<=n;i++)
68         if(chudu[i]==0&&rudu2[i]!=0)
69             ans+=dp[i];
70     printf("%d",ans);
71     return 0;
72 }