$\color{green}{<–画图不易,点下这里赞一下吧}$
啥是拓扑排序?
-
一个有向图,如果图中有入度为 0 的点,就把这个点删掉,同时也删掉这个点所连的边。
-
一直进行上面出处理,如果所有点都能被删掉,则这个图可以进行拓扑排序。
举例子
开始时,图是这样的状态,发现A
的入度为 0,所以删除A
和A
上所连的边,结果如下图:
这时发现B
的入度为 0,C
的入度为 0,所以删除B
和B
上所连的边、C
和C
上所连的边,结果如下图:
这时发现发现D
的入度为 0,所以删除D
和D
上所连的边(如果有就删),结果如下图:
这时整个图被删除干净,所有能进行拓扑排序。
解题思路
-
首先记录各个点的入度
-
然后将入度为 0 的点放入队列
-
将队列里的点依次出队列,然后找出所有出队列这个点发出的边,删除边,同事边的另一侧的点的入度 -1。
-
如果所有点都进过队列,则可以拓扑排序,输出所有顶点。否则输出-1,代表不可以进行拓扑排序。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int q[N], hh = 0, tt = -1;//队列保存入度为0的点,也就是能够输出的点,
int n, m;//保存图的点数和边数
int d[N];////保存各个点的入度
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void topsort(){
for(int i = 1; i <= n; i++){//遍历一遍顶点的入度。
if(d[i] == 0)//如果入度为 0, 则可以入队列
q[++tt] = i;
}
while(tt >= hh){//循环处理队列中点的
int a = q[hh++];
for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
int b = e[i];//a 有一条边指向b
d[b]--;//删除边后,b的入度减1
if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出,入队列
q[++tt] = b;
}
}
if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同,则可以进行拓扑排序
for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点,依次输出
cout << q[i] << " ";
}
}
else//如果队列中的点的个数与图中点的个数不相同,则可以进行拓扑排序
cout << -1;//输出-1,代表错误
}
int main(){
cin >> n >> m;//保存点的个数和边的个数
memset(h, -1, sizeof h);//初始化邻接矩阵
while (m -- ){//依次读入边
int a, b;
cin >> a >> b;
d[b]++;//顶点b的入度+1
add(a, b);//添加到邻接矩阵
}
topsort();//进行拓扑排序
return 0;
}
画图不易,求点赞~
海绵宝宝永远单身!
看一遍就懂了,思路非常清晰,tql
用队列写的,但是感觉比用数组模拟难写一点
stl队列效率很慢,最好不要用,数组模拟就好
海绵宝宝yyds
用stl的queue的写法:
雀氏牛逼,我的老baby
为什么不能用stl中的队列来做,queue不也可以存储元素吗
用的是数组模拟队列,出队元素是指针往后挪一个,但用queue就是直接出队了,用queue直接出队不好统计点数,因为点数如果小于n,要输出-1,等于的话输出序列
海绵宝宝是我的神
%%%
为啥遍历一遍顶点的入度的时候是1到n,但是输出的时候又是0到n-1啊
存储图结点的时候是点的编号是从1开始的,输出的时候是输出队列里的元素,队列中的是从0开始存储的。
提示:关于图的存储方法不明白的同学如果搜邻接表存储图搜不到想要的答案,搜一下“链式前向星”
存储图为什么有些不用add函数,而是用的bool[N][N],有什么区别呀
见算法基础课三(一)中关于图的存储的内容,使用add函数的方法对应的就是邻接表存储图,适用于稀疏图;用二维数组存储的方法对应的就是邻接矩阵存储图,适用于稠密图
海绵宝宝Yydx
有一个问题,初始化是链表的初始化,可是批注为什么是邻接矩阵呢
应该是邻接表
只是初始化头插链表的首节点为-1,h[a]存储的是a到最后插入节点的边,作为首节点,若为-1,则a没有出度边。而邻接表是整体的概念
你这个名字,不会是au的粉丝吧,hh
hh,被发现了
hh
respect
求问我的代码哪里有问题呀?编译通过但是输出总是不对
过劲哦
哪个佬能说说int e[N],ne[N],idx;分别存什么,还有e[idx]=b,ne[idx]=h[a],h[a]=idx++;啥意思呀,刚学图
https://www.acwing.com/problem/content/828/
GREAT!!!
24年研究生408统考代码题原题
wc真假?那直接写这代码能拿满分吗
必然可以
只记得思路具体解法全忘了,没想到今年考研408还考了。哎,只怪自己没做到常记常新。
你考的什么学校呀,好好奇