Pagini recente » Cod sursa (job #2646344) | Cod sursa (job #2248587) | Cod sursa (job #700949) | Cod sursa (job #2146915) | Cod sursa (job #3206292)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("sortare.in");
ofstream fout("sortare.out");
#define SI stack<int>
#define VI vector<int>
#define VB vector<bool>
#define VVI vector<VI>
int n, m;
VVI adList;
SI stiva;
VB elim;
void elimNode(int node) {
for (int i = 1; i <= n; ++i) {
for(int j = 0; j < adList[i].size(); ++j) {
if (adList[i][j] == node) {
adList[i].erase(adList[i].begin() + j);
j = adList[i].size();
}
}
}
}
void printAd() {
for (int i = 1; i <= n; ++i) {
for(auto e: adList[i]) {
fout << e << ' ';
}
fout << '\n';
}
}
int main() {
fin >> n >> m;
adList = VVI(n + 1);
elim = VB(n + 1, false);
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
adList[x].push_back(y);
}
//printAd();
bool elimAll;
do {
elimAll = true;
for (int i = n; i >= 1; --i) {
if (adList[i].empty() && !elim[i]) {
//fout << i << '\n';
stiva.push(i);
elimAll = false;
}
}
SI copy = stiva;
while (!copy.empty()) {
if (!elim[copy.top()]) {
elim[copy.top()] = true;
elimNode(copy.top());
}
copy.pop();
}
} while(!elimAll);
while (!stiva.empty()) {
fout << stiva.top() << ' ';
stiva.pop();
}
}
//caut in adList[n] daca gasesc size == 0, caz in care