网站建设基本知识代码,大学制作网站怎么做,番禺做网站600元,开购物网站需要多少钱目录
查找文献
P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
有向图的拓扑序列
848. 有向图的拓扑序列 - AcWing题库 最大食物链计数
P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 查找文献
P5318 【深基18.例3】…目录
查找文献
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 bits/stdc.h
#define int long long
const int N 2e510;
std::vectorstd::vectorint g(N);
bool vis[N]{};
void dfs(int cur)
{std::coutcur ;vis[cur]true;for(int i 0;i g[cur].size();i ){if(vis[g[cur][i]]false)dfs(g[cur][i]);}
}
void bfs()
{memset(vis,false,sizeof(vis));std::queueint q;q.push(1);vis[1]true;while(!q.empty()){int curq.front();std::coutcur ;q.pop();for(int i 0;i g[cur].size();i ){if(vis[g[cur][i]]false){vis[g[cur][i]]true;q.push(g[cur][i]);}}}
}
signed main()
{int n,m;std::cin n m;for(int i 1;i m;i ){int u,v;std::cin u v;g[u].push_back(v);}for(int i 1;i n;i ){std::sort(g[i].begin(),g[i].end());}dfs(1);std::cout\n;bfs();return 0;
}
有向图的拓扑序列
848. 有向图的拓扑序列 - AcWing题库
这道题是拓扑排序的模板题
拓扑图就是有向无环图
使用bfs进行广搜
1.选择一个入度为0的点并进行输出
2.删掉这个点并且删除后面所有的出边
3.重复步骤1和2直到所有的点都被输出
完整代码
#include bits/stdc.h
#define int long long
const int N 2e5 10;
std::vectorstd::vectorint g(N);
int d[N], ans[N];
int num 0;
int n, m;
std::queueint q;
void bfs() {while (!q.empty()) {int cur q.front();q.pop();ans[num] cur;for (int i 0; i g[cur].size(); i) {d[g[cur][i]]--;if (d[g[cur][i]] 0)q.push(g[cur][i]);}}
}
signed main() {std::cin n m;for (int i 1; i m; i) {int u, v;std::cin u v;g[u].push_back(v);d[v];}for (int i 1; i n; i) {if (!d[i]) {q.push(i);}}bfs();//std::coutnum;if (num n) {for (int i 0; i num; i) {std::cout ans[i] ;}} elsestd::cout -1;return 0;
} 最大食物链计数
P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
食物链只有捕食和被捕食的关系不存在平级的关系所以想到了拓扑排序
思路
用二维vector存图数组in和数组out分别存节点的入度数和出度数再开一个f数组存路径如果搜到了入度为0的即食物链低端就进入队列每次搜索的时候节点的路径叠加并且清空这个点的出度的边再循环
最后遍历一遍如果搜到了出度为0的点即食物链顶端那么答案加上这个数
记得取模
完整代码
#include bits/stdc.h
#define int long long
const int N 5e510;
const int mod 80112002;
std::vectorstd::vectorintg(N);
int in[N],out[N];//入度出度
int f[N];//路径
std::queueint q;
void bfs()
{while(!q.empty()){int curq.front();q.pop();for(int i 0;i g[cur].size();i ){int nextg[cur][i];in[next]--;if(in[next]0)q.push(next);f[next](f[next]f[cur])%mod;}}
}
signed main()
{int n,m;std::cin n m;for(int i 1;i m;i ){int u,v;std::cin u v;g[u].push_back(v);in[v];out[u];}for(int i 1;i n;i ){if(in[i]0){q.push(i);f[i]1;}}bfs();int ans0;for(int i 1;i n;i ){if(out[i]0)ans(ansf[i])%mod;}std::coutans;return 0;
}
