数学联邦政治世界观
超小超大

数学(三)

一个有向无环图,如果图中有入度为 0 的点,就把这个点删掉,同时也删掉这个点所连的边。

一直进行上面出处理,如果所有点都能被删掉,则这个图可以进行拓扑排序。

典型代表:食物链

参考代码如下

include:<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;

int h[N], e[N], ne[N], idx;//存图

int in[N]; // 存储每个结点的入度

void add(int a, int b)

{

e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}

bool topsort() {

vector<int> L;

queue<int> S;

for (int i = 1; i <= n; i++) {//遍历一遍顶点的入度。

if (!in[i]) S.push(i);

}//如果入度为 0, 则可以入队列

while (!S.empty()) { //循环处理队列中入度为0的点

int u = S.front();

S.pop();

L.push_back(u);

for (int i = h[u]; i != -1; i = ne[i]) //循环删除 u 发出的边

{

int j = e[i];//a 有一条边指向b

if (--in[j] == 0) //删除边后,b的入度减1

S.push(j);//如果b的入度减为 0,则 b 可以输出,入队列

}

}

if (L.size() == n)//如果队列中的点的个数与图中点的个数相同,则可以进行拓扑排序

{

for (auto i: L) cout << i << ' ';//队列中保存了所有入度为0的点,依次输出

return true;

} else return false;

}

int main()

{

cin>>n>>m;

memset(h, -1, sizeof h);

for (int i = 1; i <= m; i ++ )

{

int a, b;

cin>>a>>b;

add(a, b);

in[b] ++ ;

}

if (!topsort()) puts("-1");

return 0;

}

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

默祈 连载中
默祈
古灵精怪爱丽丝
父母被怪物害死的小默羽拼了命逃到教堂保住了性命,成为了看守神明法宝的一位小咯咯。但有一天,宝物意外失踪了,而所有的一切罪责和嫌疑都纷纷指向了......
2.8万字2个月前
疯子又来啦! 连载中
疯子又来啦!
星光曰月
天赐降福佑我族道却何曾手下留天道若不吾存留反了这天又如何回魂肉魄轮回尽,亦是相回白雪纷。每世抗命残伤奄,血发污衣浸红身。自曾梦影现故因,终是......
1.8万字2个月前
六芒星之旅 连载中
六芒星之旅
白井空慕
即将成为下一位新神的白玖,在历练时经历的种种事情与磨难,最后迎来的会是什么?是要坚持自己的决定与旧神卡维斯特抗争还是归顺于他,成为傀儡?
2.1万字2个月前
重生?迪恩你个老六! 连载中
重生?迪恩你个老六!
罪恶中介阎君
机设,男迪,非拟人动画迪预警!迪恩重生后开始“摆烂”,剧情又会按照怎样的方向发展呢?作者雷迪息!!!
3.0万字2个月前
午夜图书馆探索异世界 连载中
午夜图书馆探索异世界
逆卷灵
艾米丽站在画面的前景,她手持一把古铜色的钥匙,钥匙上刻有复杂的符号,散发着微弱的光芒。她的表情既紧张又坚定,目光直视前方。
4.1万字2个月前
源于创作的故事 连载中
源于创作的故事
创造者小桉
故事中,一个15岁的女孩dawn是一位小作家,某天,她笔下的人物来到了她的世界,他们会发生怎样的故事呢
1.8万字2个月前