当前位置:网站首页>【图论】拓扑排序
【图论】拓扑排序
2022-07-04 22:30:00 【你算哪一个bug?】
拓扑排序的概念等不赘述了。
拓扑排序的方法
描述拓扑排序的图中主要维护这几个结构,其中邻接表负责描述点与点之间边的关系。
拓扑排序的操作
代码实现
拓扑排序(Topological Sorting)_神奕的博客-CSDN博客_拓扑排序
代码上我是照着他的入门的
题目
2367 – Genealogical tree (poj.org)
模板题,构建一个图,再排序输出即可。
oj不支持C++11,得把auto换成迭代器…
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
#define N 1000
queue<int>output;
class Graph
{
public:
Graph(int v)//顶点个数初始化,new邻接表,把入度集合全部初始化为0
{
_v = v;
_adj = new list<int>[v];//new一个有v个顶点的邻接表
_indegree.resize(v, 0);//初始化入度集合
}
~Graph()
{
delete[] _adj;
}
void addEdge(int val, int w)//值为val的点指向w
{
_adj[val].push_back(w);
_indegree[w]++;
}
bool topological_sort()
{
for (int i=1;i<_indegree.size();i++)//入队结点其实还存在一层映射
{
if (!_indegree[i])
{
_q.push(i);
}
}
int count = 0;
while (!_q.empty())
{
int v = _q.front();
_q.pop();
output.push(v);
count++;
//更新入度集合,把入度为0的点入队
list<int>::iterator it = _adj[v].begin();
for (;it!=_adj[v].end();it++)
{
_indegree[*it]--;
if (!_indegree[*it])
{
_q.push(*it);
}
}
}
if (count<_v)//图有回路
{
return false;
}
else
{
return true;
}
}
private:
int _v;//顶点个数
list<int>* _adj;//邻接表
queue<int>_q;//维护入度为0的顶点的集合
vector<int> _indegree;//记录每个顶点的入度
};
int main()
{
int n;
cin >> n;
Graph g(n+1);
for (int i = 1; i <= n; i++)
{
int x;
while (cin >> x)
{
if (x == 0)
{
break;
}
g.addEdge(i, x);
}
}
g.topological_sort();
bool flag = 1;
while (!output.empty())
{
int x = output.front();
output.pop();
if (flag)
{
cout << x;
flag = 0;
}
else
{
cout << " " << x;
}
}
return 0;
}
边栏推荐
- Attack and defense world misc master advanced zone 001 normal_ png
- 攻防世界 MISC 进阶区 hit-the-core
- Persistence mechanism of redis
- Test will: bug classification and promotion solution
- Why is Dameng data called the "first share" of domestic databases?
- MySQL Architecture - logical architecture
- [Lua] Int64 support
- Google Earth Engine(GEE)——以MODIS/006/MCD19A2为例批量下载逐天AOD数据逐天的均值、最大值、最小值、标准差、方差统计分析和CSV下载(北京市各区为例)
- Redis入门完整教程:初识Redis
- [OpenGL] note 29 anti aliasing (MSAA)
猜你喜欢
sobel过滤器
Duplicate ADMAS part name
Unity vscode emmylua configuration error resolution
10 schemes to ensure interface data security
Redis入门完整教程:GEO
Logo Camp d'entraînement section 3 techniques créatives initiales
攻防世界 misc 高手进阶区 a_good_idea
Attack and defense world misc advanced area ditf
How to send a reliable request before closing the page
Serial port data frame
随机推荐
图片懒加载的原理
新版判断PC和手机端代码,手机端跳转手机端,PC跳转PC端最新有效代码
[try to hack] wide byte injection
leetcode 72. Edit distance edit distance (medium)
Li Kou 98: verify binary search tree
Redis入门完整教程:Redis Shell
Talk about Middleware
Attack and defense world misc master advanced zone 001 normal_ png
NFT insider 64: e-commerce giant eBay submitted an NFT related trademark application, and KPMG will invest $30million in Web3 and metauniverse
SPSS安装激活教程(包含网盘链接)
Google Earth engine (GEE) - tasks upgrade enables run all to download all images in task types with one click
【剑指Offer】6-10题
Unity修仙手游 | lua动态滑动功能(3种源码具体实现)
关于栈区、堆区、全局区、文字常量区、程序代码区
Redis démarrer le tutoriel complet: Pipeline
MySQL Architecture - user rights and management
Why is Dameng data called the "first share" of domestic databases?
记录:关于Win10系统中Microsoft Edge上的网页如何滚动截屏?
9 - 类
蓝队攻防演练中的三段作战