洛谷P4017 最大食物链计数
2024-09-06 07:06:46
拓扑排序板子题
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
//Mystery_Sky
//
#define maxn 1000010
#define maxm 5000050
#define mod 80112002
struct Road{
int next;
int to;
};
Road road[maxn];
int head[maxm], cnt;
inline void add_edge(int u, int v) {
road[++cnt].to = v;
road[cnt].next = head[u];
head[u] = cnt;
} int ind[maxn], eat[maxn];
int d[maxn];
int n, m;
queue <int> q; inline void topo() {
for(int i = ; i <= n; i++) {
if(!ind[i]) {
q.push(i);
d[i]++;
}
} while (!q.empty()) {
int now = q.front();
q.pop();
for(int i = head[now]; i; i = road[i].next) {
int e = road[i].to;
d[e] = (d[e] + d[now]) % mod;
if(! --ind[e]) q.push(e);
}
}
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
add_edge(a, b);
ind[b]++;
eat[a]++;
}
topo();
int ans = ;
for(int i = ; i <= n; i++) {
if(!eat[i]) ans = (ans + d[i]) % mod;
}
printf("%d\n", ans);
return ;
}
最新文章
- Solr Python API : SolrCloudpy 与 Pysolr 的 对比
- C++ 之 策略模式
- windows7打印时,显示脱机,提示“服务器打印后台处理程序服务没有运行”。
- EXCEL计算数字、汉字、英文单元格的计数
- vi编辑器的简单使用
- [zt]不到最后一秒你永远不知道结局且震撼你心灵的高端电影
- android小细节
- (3)选择元素——(9)为交替的列加样式(Styling alternate rows)
- hdu 1241 Oil Deposits_dfs or bfs
- 把C#对象变成数组技术---索引器(indexer)
- 解析java中volatile关键字
- Win7怎样禁用自带IE浏览器
- 201521123053《Java程序设计》第四周总结
- php 在foreach中循环数组的时候添加元素的属性
- C#项目中操作Excel文件——使用NPOI库
- git 在本地拉取远程分支的代码(并不做提交操作)
- django models数据库操作
- java线程执行的优先级
- ADT和DS
- js异步处理工作机制