C++ 算法学习 - 1.3 拓扑排序
最编程
2024-10-06 16:13:34
...
拓扑排序:对有向无环图(DAG)中所有顶点的一种线性排序,使得图中任意一条有向边的指向顶点在排序中都排在起始顶点之前。
换句话说,如果图中存在一条从顶点A到顶点B的有向边,那么在拓扑排序中,顶点A会排在顶点B的前面。
一般使用DFS或BFS来实现.
P1. 洛谷p4017最大食物链计数
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int ans=0;
int lowwest,highest;
class Graph {
public:
int V; // 顶点数量
std::vector<std::vector<int>> adjList; // 邻接表
std::vector<bool> visited; // 记录顶点是否被访问过
public:
Graph(int vertices) : V(vertices) {
adjList.resize(V+1);
visited.resize(V+1, false);
}
void addEdge(int u, int v) {
// 在顶点u的邻接表中添加顶点v
adjList[u].push_back(v);
}
// 广度优先搜索
void BFS(int startVertex) {
std::queue<int> q;
q.push(startVertex);
while (!q.empty()) {
int currentVertex = q.front();
q.pop();
if (currentVertex==lowwest) ans=(ans+1)%80112002;//高精度处理结果的方式
for (int neighbor : adjList[currentVertex]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
};
int main()
{
int n,m;
cin>>n>>m;
Graph mygraph(n);
for(int i=1;i<=m;i++)
{
int a,b;cin>>a>>b;
mygraph.addEdge(b,a);
mygraph.visited[a]=1;//此处赋予visited的意义是:如果为1则代表有生物吃它
}
for(int i=1;i<=n;i++)
{
if(mygraph.visited[i]==0) highest=i;
if(mygraph.adjList[i].size()==0) lowwest=i;
}
//cout<<lowwest<<" "<<highest;
mygraph.BFS(highest);
cout<<ans;
return 0;
}
下一篇: MFC 多媒体计时器示例(源代码下载)