目录
查找文献
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] << " ";
}
} else
std::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;
}
