目录
查找文献
P5318 【深基18.例3】查找文献 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
有向图的拓扑序列
848. 有向图的拓扑序列 – AcWing题库
最大食物链计数
P4017 最大食物链计数 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
查找文献
P5318 【深基18.例3】查找文献 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题之前写过,但不太熟练,今天再来写一次
思路:要求输出dfs和bfs两种遍历情况
题目中说了要排序,所以先得把图中每个点先排序
dfs是深搜,搜到了没有遍历过的点就继续进入dfs,类似于递归
bfs是宽搜,建立一个int类型的队列,把没有搜到过的点全部入队并标记,由于循环是在队列里面进行的,所以函数不需要传参进去,最开始1文献入队就行了
完整代码:
#include
#define int long long
const int N = 2e5+10;
std::vector> g(N);
bool vis[N]{};
void dfs(int cur)
{
std::cout q;
q.push(1);
vis[1]=true;
while(!q.empty())
{
int cur=q.front();
std::cout> n >> m;
for(int i = 1服务器托管网;i > u >> v;
g[u].push_back(v);
}
for(int i = 1;i
有向图的拓扑序列
848. 有向图的拓扑序列 – AcWing题库
这道题是拓扑排序的模板题
拓扑图就是有向无环图
使用bfs进行广搜
1.选择一个入度为0的点,并进行输出
2.删掉这个点,并且删除后面所有的出边
3.重复步骤1和2,直到所有的点都被输出
完整代码:
#include
#define int long long
const int N = 2e5 + 10;
std::vector> g(N);
int d[N], ans[N];
int num = 0;
int n, m;
std::queue q;
void bfs() {
while (!q.empty()) {
int cur = q.front();
q.pop();
ans[num++] = cur;
for (int i = 0; i > n >> m;
for (int i = 1; i > u >> v;
g[u].push_back(v);
d[v]++;
}
for (int i = 1; i
最大食物链计数
P4017 最大食物链计数 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
食物链,只有捕食和被捕食的关系,不存在平级的关系,所以想到了拓扑排序
思路:
用二维vector存图,数组in和数组out分别存节点的入度数和出度数,再开一个f数组存路径,如果搜到了入度为0的(即食物链低端),就进入队列,每次搜索的时候节点的路径叠加,并且清空这个点的出度的边,再循环
最后遍历一遍,如果搜到了出度为0的点(即食物链顶端),那么答案加上这个数
记得取模
完整代码:
#include
#define int long long
const int N = 5e5+10;
const int mod = 8服务器托管网0112002;
std::vector>g(N);
int in[N],out[N];//入度,出度
int f[N];//路径
std::queue q;
void bfs()
{
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i = 0;i > n >> m;
for(int i = 1;i > u >> v;
g[u].push_back(v);
in[v]++;
out[u]++;
}
for(int i = 1;i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
声明,定义,以及链接规范 翻译单元 声服务器托管网明与定义 链接规范 C/C++ 内存布局 可执行映像 程序堆栈 动态分配的堆 对象的内存布局 kilobyte 和 kibibyte服务器托管网 流水线缓存以及优化 未完待续。。。 服务器托管,北京服务器托管,…