Pagini recente » Cod sursa (job #2910137) | Cod sursa (job #2336562) | Cod sursa (job #358115) | Cod sursa (job #2533112) | Cod sursa (job #2615207)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAX_N 100
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 depths[MAX_N + 1] = {0};
int node;
for (i = 1; i <= n; i++) {
if (gr_ext[i] == 0) {
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++) {
if (!depths[*it]) {
q.push(*it);
new_length++;
pq.push({depth, *it});
} else if (depth > depths[*it]) {
depths[*it] = depth;
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++) {
depths[i] = 0;
}
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);
}
}
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;
}