关于拓扑排序
  • 板块学术版
  • 楼主WhileTrueRP
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/7 10:52
  • 上次更新2023/11/2 15:05:43
查看原帖
关于拓扑排序
373198
WhileTrueRP楼主2023/10/7 10:52

求助: 1.以下算法是否为拓扑排序?

2.以下算法是否是排序?

3.有无hack数据(n<1e4,ai<1e9)。

#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 1e7 + 3;
int n, ot;
int t[MAXN], deg[MAXN], head[MAXN];
struct graph {
	int nxt, to;
} a[MAXN];
void add(int x, int y) {
	a[++ot] = {head[x], y};
	head[x] = ot;
	deg[y]++;
}
int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; ++i)	cin >> t[i];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j)
			if (t[i] < t[j])	add(i, j); //连一条i->j的边
	}
	queue<int> q;
	for (int i = 1; i <= n; ++i)	if (!deg[i])	q.push(i);
	while (!q.empty()) {
		int no = q.front();
		cout << t[no] << " ";
		q.pop();
		for (int i = head[no]; i; i = a[i].nxt) {
			int y = a[i].to;
			deg[y]--;
			if (!deg[y])	q.push(y);
		}
	}
	return 0;
}
2023/10/7 10:52
加载中...