P4017 最大食物链计数-拓扑排序
P4017 最大食物链计数
题目来源-洛谷
题意
要求最长食物链的数量。按照题意，最长食物链就是指有向无环图DAG中入度为０到出度为０的不同路径的数量（链数）
思路
-
在计算时，明显：一个被捕食者所在节点的食物链路径是其所有捕食者的路径条数之和，要计算k节点所在的链数，必须清楚其所有入度节点的链数。即存在拓扑排序
-
因此借助拓扑排序的方法：计算所有食物链数量＝计算每个食物链终点的节点（出度为０的节点）的路径树之和
-
建立队列，所有入度为０的节点入队，初始值为１
-
遍历，取出队首元素ｋ节点，遍历其相邻的子节点（被捕食者），让其子节点的食物链数量值得＋ｋ节点的数，并让其子节点入度为－１。若该节点入度为0则推入队。
-
重复第二遍操作
-
遍历所有出度为0 的节点（说明这些这些节点所在的最大链不会完全相交-是相对独立的食物链），例如5和6两个节点
-
数据约束
注意数组范围即可
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int m,n;//n个点m条边
vector<int> p[MAXN];//邻接表存图
int rd[MAXN],cd[MAXN];
queue<int> q;
int ans[MAXN],num = 0;
int main(){ int x,y;cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;p[x].push_back(y);cd[x]++;//出度+1 -作为捕食者 rd[y]++;//入度+1 作为被捕食者 }//拓扑排序 //从食物链的起点 即入度为0的点for(int i=1;i<=n;i++) {if(rd[i] == 0){q.push(i);ans[i] = 1;//初始链设为1 }}while(!q.empty()){int t = q.front();q.pop();for(int i=0;i<p[t].size();i++){int k = p[t][i];//遍历到的节点设置为k ans[k] = (ans[t]+ans[k])%80112002 ;//食物链相加 rd[k] --; //该链计算过了 if(rd[k]==0){ //作为捕食者 q.push(k);}}}//遍历找出度为0的点-说明是已经找到了食物链的终点 for(int i=1;i<=n;i++){if(cd[i]==0){num = (num+ ans[i])%80112002;//所有不相交的食物链加起来 }} cout<<num; return 0;
}