当前位置: 首页> 房产> 建材 > 国内重大新闻事件2024_免费域名申请 知乎_佛山百度seo代理_seo搜索引擎排名优化

国内重大新闻事件2024_免费域名申请 知乎_佛山百度seo代理_seo搜索引擎排名优化

时间:2025/7/10 18:02:57来源:https://blog.csdn.net/2301_81772249/article/details/146589911 浏览次数:0次
国内重大新闻事件2024_免费域名申请 知乎_佛山百度seo代理_seo搜索引擎排名优化

拓扑排序是一种无环的有向图的排序,了解拓扑排序之前,我们先了解一下什么是AOV图

AOV网不能有回路,不然就不能确定先后次序了

拓扑排序的目标就是把有向无环图中的所有结点排序,使得排在前面的结点不会依赖后面的结点

流程如下:step1:找到所有入度为0的点,加入到队列中

 step2:依次删除队列里的队头结点,每次删除的时候把连着该结点的边也删掉,并且把新的入度为0的点加入进来

step3:直到队列中没有结点了,此时排序结束

如果队列里有环,是不能把所有结点都排上序的,所以拓扑排序还可以判断图里有没有环

具体流程

好的,我们来做一下模板题

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
int in[N];
int n;
vector<int> edges[N];
int main()
{cin >> n;for(int i = 1;i<=n;i++){int x;while(cin>>x,x){edges[i].push_back(x);in[x]++;}}queue<int> q;for(int i = 1;i<=n;i++){if(in[i]==0) q.push(i);}while(q.size()){auto t = q.front();q.pop();cout << t << " ";for(auto &e : edges[t]){in[e]--;if(in[e]==0){q.push(e);}}}return 0;
}

关键字:国内重大新闻事件2024_免费域名申请 知乎_佛山百度seo代理_seo搜索引擎排名优化

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: