2024/2/12 图的基础知识 2

目录

查找文献

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;
}