当前位置: 首页 > news >正文

关于做展厅的网站广州线下教学

关于做展厅的网站,广州线下教学,wordpress 瀑布流 插件,邯郸做网站哪家好目录 查找文献 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 = 2e5+10;
std::vector<std::vector<int>> g(N);
bool vis[N]{};
void dfs(int cur)
{std::cout<<cur<<" ";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::queue<int> q;q.push(1);vis[1]=true;while(!q.empty()){int cur=q.front();std::cout<<cur<<" ";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::vector<std::vector<int>> g(N);
int d[N], ans[N];
int num = 0;
int n, m;
std::queue<int> 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::cout<<num;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 = 5e5+10;
const int mod = 80112002;
std::vector<std::vector<int>>g(N);
int in[N],out[N];//入度,出度
int f[N];//路径
std::queue<int> q;
void bfs()
{while(!q.empty()){int cur=q.front();q.pop();for(int i = 0;i < g[cur].size();i ++){int next=g[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 ans=0;for(int i = 1;i <= n;i ++){if(out[i]==0)ans=(ans+f[i])%mod;}std::cout<<ans;return 0;
}

http://www.dinnco.com/news/34726.html

相关文章:

  • 如何做网站视频模板个人网站源码免费下载
  • 网站建设行业发展史西安百度推广电话
  • 前端做网站查权重网站
  • 湛江网站设计哪家好乐陵市seo关键词优化
  • 怎么做公司网站的手机客户端软文写作的基本要求
  • 网站建设与维护怎么学全媒体运营师报考官网在哪里
  • 江宁网站建设域名流量查询工具
  • 大庆做网站公司品牌运营推广方案
  • 辽宁省建设机械协会官方网站搜索图片识别
  • 石家庄网站建设招商学设计什么培训机构好
  • 网址ip域名解析北京网站建设优化
  • 中国查企业的网站谈谈你对seo概念的理解
  • 石家庄建设学校冯耀宗seo博客
  • 做网站要注册公司么全媒体广告策划营销
  • 蔬菜基地做网站合适吗seo推广怎么样
  • 怎么做游戏平台网站设计网站用什么软件
  • 中国商标网官网入口武汉抖音seo搜索
  • 做网站设计公司价格2345网址导航大全
  • 大连政府建设工程信息网站seo关键词优化要多少钱
  • 全国建设厅网站百度最新秒收录方法2023
  • 做网站什么时候注册商标中国疾控卫生应急服装
  • thinkcmf做网站快不快网络服务器是指什么
  • 哪个网站使用vue 做的国外比较开放的社交软件
  • 网站建设和管理百度经验首页官网
  • 学做窗帘要下载哪个网站上海今天发生的重大新闻
  • 公司网站推广计划书怎么做直播营销的优势有哪些
  • 做网站开发最多能做几年网店推广方案范文
  • 天津怎么建立企业网站适合奖励自己的网站免费
  • 网站建设收费标准报价看广告收益的正规平台
  • 徐州党廉政建设网站足球比赛直播