Mai intai trebuie sa te autentifici.

Cod sursa(job #2707056)

Utilizator teofilotopeniTeofil teofilotopeni 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;
}