彩票资料网站怎么做,网站开发项目计划书ppt,中国建材工程建设协会网站,传奇官网目录 1 基础知识2 模板3 工程化 1 基础知识
拓扑序列#xff1a;针对有向图而言#xff0c;该序列内#xff0c;所有边都是从前指向后的。
如果存在环#xff0c;那么该图一定不存在拓扑序列。否则#xff0c;一定存在拓扑序列。
有向图中的入度和出度。 入度为0的结点… 目录 1 基础知识2 模板3 工程化 1 基础知识
拓扑序列针对有向图而言该序列内所有边都是从前指向后的。
如果存在环那么该图一定不存在拓扑序列。否则一定存在拓扑序列。
有向图中的入度和出度。 入度为0的结点可以作为拓扑序列的起点。
求拓扑序列的关键步骤
把入度为0的结点插入队列q。弹出队头t遍历队头t的下一个结点将其入度减1。操作之后如果其值为0则插入队列q。重复进行步骤2直至队列q为空。
2 模板
题目1给出结点数目n和边数m以及一系列的边如果此图存在拓扑序列请输出输出任意一种拓扑序列即可否则输出-1。
#include iostream
#include vector
#include queueusing namespace std;const int N 1e5 10;
int n, m;
vectorvectorint g(N);
vectorint d(N); //存储每个结点的入度int main() {cin n m;int x, y;while (m--) {cin x y;//添加x到y的边g[x].emplace_back(y);d[y];}queueint q;for (int i 1; i n; i) {if (d[i] 0) {q.push(i);}}vectorint res;while (!q.empty()) {auto t q.front();res.emplace_back(t); //存入向量res中 q.pop();//t可以走到哪里for (auto x : g[t]) {//把结点t删除d[x]--;if (d[x] 0) {q.push(x);}}}if (res.size() n) {for (int i 0; i n; i) cout res[i] ;cout endl;} else {puts(-1);}return 0;
}3 工程化
暂无。。。
