Pagini recente » Cod sursa (job #2480333) | Cod sursa (job #1622620) | Cod sursa (job #2343151) | Cod sursa (job #77251) | Cod sursa (job #1770311)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main() {
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
int n, m, x, y;
cin>>n>>m;
vector<int> sorted;
map<int, bool> isIncluded;
vector< vector<int> > graf(n+1);
vector< map<int, bool> > parents(n+1);
for (int i = 0; i < m; i++) {
cin>>x>>y;
graf[x].push_back(y);
parents[y][x] = true;
//cout<<x<<" "<<y<<" "<<parents[y].size()<<"\n";
}
vector<int> a;
for (int i = 1; i <= n; i++) {
if (parents[i].size() == 0) {
a.push_back(i);
//cout<<i<<" ";
}
}
//cout<<"\n";
while (sorted.size() < n) {
for (int i = 0; i < a.size(); i++) {
sorted.push_back(a[i]);
}
vector<int> a2;
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < graf[a[i]].size(); j++) {
if (parents[graf[a[i]][j]].size() > 0) {
parents[graf[a[i]][j]].erase(a[i]);
}
if (!isIncluded[graf[a[i]][j]] && parents[graf[a[i]][j]].size() == 0) {
a2.push_back(graf[a[i]][j]);
isIncluded[graf[a[i]][j]] = true;
}
}
}
a = a2;
}
for (int i = 0; i < sorted.size(); i++) {
cout<<sorted[i]<<" ";
}
}