Mai intai trebuie sa te autentifici.
Cod sursa(job #2707056)
Utilizator | Data | 16 februarie 2021 13:43:55 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.17 kb |
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
// Sortare topologica
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m, x, y;
scanf("%d %d", &n, &m);
deque<int> coada, empty;
vector<deque<int>::iterator> elemente(n + 1, empty.begin());
while (m--) {
scanf("%d %d", &y, &x);
if (elemente[x] != empty.begin() && elemente[y] != empty.begin()) {
if (elemente[x] > elemente[y]) { // change pozition of first
coada.erase(elemente[x]);
elemente[x] = coada.insert(elemente[y], x);
}
}
else if (elemente[x] != empty.begin()) // add second
elemente[y] = coada.insert(elemente[x] + 1, y);
else if (elemente[y] != empty.begin()) // add first
elemente[x] = coada.insert(elemente[y], x);
else { // add both
elemente[x] = coada.end();
coada.push_back(x);
elemente[y] = coada.end();
coada.push_back(y);
}
}
for (; coada.size(); coada.pop_back())
printf("%d ", coada.back());
return 0;
}