当前位置:网站首页>【图论】拓扑排序
【图论】拓扑排序
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
- Lost in the lock world of MySQL
- 都说软件测试很简单有手就行,但为何仍有这么多劝退的?
- Redis: redis configuration file related configuration and redis persistence
- Sword finger offer 67 Convert a string to an integer
- 攻防世界 MISC 高手进阶区 001 normal_png
- Google Earth engine (GEE) - globfire daily fire data set based on mcd64a1
- Microservices -- Opening
- SQL中MAX与GREATEST的区别
- md5工具类
猜你喜欢
The overview and definition of clusters can be seen at a glance
Redis入门完整教程:有序集合详解
Lost in the lock world of MySQL
Redis入门完整教程:HyperLogLog
The Sandbox 和数字好莱坞达成合作,通过人力资源开发加速创作者经济的发展
都说软件测试很简单有手就行,但为何仍有这么多劝退的?
SPSS installation and activation tutorial (including network disk link)
Redis入门完整教程:初识Redis
Why is Dameng data called the "first share" of domestic databases?
Business is too busy. Is there really no reason to have time for automation?
随机推荐
Redis入门完整教程:事务与Lua
Attack and defense world misc advanced area can_ has_ stdio?
How can enterprises cross the digital divide? In cloud native 2.0
攻防世界 MISC 进阶区 Ditf
串口数据帧
Hit the core in the advanced area of misc in the attack and defense world
LOGO特训营 第二节 文字与图形的搭配关系
页面关闭前,如何发送一个可靠请求
Why is Dameng data called the "first share" of domestic databases?
Attack and Defense World MISC Advanced Area Erik baleog and Olaf
攻防世界 misc 进阶区 2017_Dating_in_Singapore
繁华落尽、物是人非:个人站长该何去何从
Locust performance test - environment construction and use
Tla+ introductory tutorial (1): introduction to formal methods
Sword finger offer 68 - ii The nearest common ancestor of binary tree
剑指Offer 68 - II. 二叉树的最近公共祖先
攻防世界 MISC 進階區 Erik-Baleog-and-Olaf
9 - class
关于栈区、堆区、全局区、文字常量区、程序代码区
Practice and principle of PostgreSQL join