Pagini recente » Cod sursa (job #1534721) | Cod sursa (job #1427079) | Cod sursa (job #90780) | Cod sursa (job #1629503) | Cod sursa (job #2615235)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAX_N 50000
struct per {
int x, y;
bool operator<(const per& rhs) const {
if (x != rhs.x) {
return x < rhs.x;
}
return y < rhs.y;
}
};
int toposort(std::vector<int> adj[], int n, int *gr_ext) {
int i, j, depth = 0, l = 0, length = 1, new_length = 0;
std::queue<int> q;
//std::priority_queue<per> pq;
int v[MAX_N + 1], len = 0;
int visited[MAX_N + 1] = {0};
int node;
for (i = 1; i <= n; i++) {
if (gr_ext[i] == 0) {
v[len++] = i;//pq.push({depth, i});
q.push(i);
}
}
depth++;
while (!q.empty()) {
node = q.front();
q.pop();
for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
gr_ext[*it]--;
if (!visited[*it]) {
q.push(*it);
new_length++;
visited[*it] = 1;
}// else if (depth > depths[*it]) {
// depths[*it] = depth;
//pq.push({depth, *it});
// }
if (gr_ext[*it] == 0) {
v[len++] = *it;//pq.push({depth, *it});
}
}
l++;
if (l >= length) {
length = new_length;
new_length = 0;
l = 0;
depth++;
}
}
struct per pp;
for (i = 1; i <= n; i++) {
//pp = pq.top();
//pq.pop();
//while (depths[pp.y] != 0) {
// pp = pq.top();
// pq.pop();
//}
//depths[pp.y] = 1;
//printf("%d ", pp.y);
printf("%d ", v[len - i]);
}
}
int main() {
int i, j, n, m, x, y;
std::vector<int> adj[MAX_N + 1];
int gr_ext[MAX_N + 1] = {0};
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d\n", &n, &m);
while (m--) {
scanf("%d %d", &x, &y);
gr_ext[x]++;
adj[y].push_back(x);
}
int *ans = (int*)malloc(100 * sizeof(int));
toposort(adj, n, gr_ext);
return 0;
}