怎么在百度上建立网站,玻璃制品东莞网站建设,网站建设怎样才能吸引顾客,中国建设银行积分换购网站Description 如图所示为某生态系统的食物网示意图#xff0c;据图回答第1小题现在给你n个物种和m条能量流动关系#xff0c;求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独… Description 如图所示为某生态系统的食物网示意图据图回答第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条能量流动关系。 数据保证输入数据符号生物学特点且不会有重复的能量流动关系出现 1N100000 0m200000 题目保证答案不会爆 int 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 9 出生物题是什么心态 一条食物链就是从0入度节点到0出度节点的一条路径而这又是一个DAG所以拓扑排序后随便DP一下就好了。 #includecstdio
#includecctype
#includequeue
#includecstring
#includealgorithm
#define rep(i,s,t) for(int is;it;i)
#define dwn(i,s,t) for(int is;it;i--)
#define ren for(int ifirst[x];i;inext[i])
using namespace std;
const int BufferSize116;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {if(headtail) {int lfread(buffer,1,BufferSize,stdin);tail(headbuffer)l;}return *head;
}
inline int read() {int x0,f1;char cGetchar();for(;!isdigit(c);cGetchar()) if(c-) f-1;for(;isdigit(c);cGetchar()) xx*10c-0;return x*f;
}
const int maxn100010;
const int maxm200010;
typedef long long ll;
int n,m,first[maxn],deg[maxn],in[maxn],is[maxn],next[maxm],to[maxm],e;
void AddEdge(int u,int v) {in[v];deg[v];is[u]1;to[e]v;next[e]first[u];first[u]e;
}
int Q[maxn],f[maxn],g[maxn];
int main() {nread();mread();rep(i,1,m) AddEdge(read(),read());int l1,r0;rep(i,1,n) if(!in[i]) Q[r]i,f[i]1;while(lr) {int xQ[l];ren {f[to[i]]f[x];if(!(--in[to[i]])) Q[r]to[i];}}int ans0;rep(i,1,n) if(!is[i]deg[i]) ansf[i];printf(%d\n,ans);return 0;
}转载于:https://www.cnblogs.com/wzj-is-a-juruo/p/5552671.html
