求助: 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;
}