Pagini recente » Cod sursa (job #266026) | Cod sursa (job #465690) | Cod sursa (job #2329186) | Cod sursa (job #826148) | Cod sursa (job #1705795)
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
typedef unsigned int uint;
using namespace std;
vector <vector<int> > arce;
ofstream out("sortaret.out");
void topsort(vector<int>& grad_in, int n) {
stack<int> s;
for (int i = 1; i <=n; ++i)
if (grad_in[i] == 0)
s.push(i);
vector<int> result;
while(!s.empty()) {
int nod = s.top();
s.pop();
result.push_back(nod);
for (uint i = 0; i < arce[nod].size(); ++i) {
--grad_in[arce[nod][i]];
if (grad_in[arce[nod][i]] == 0)
s.push(arce[nod][i]);
}
}
for (uint i = 0; i < result.size(); ++i)
out << result[i] << " ";
out << '\n';
}
int main() {
ifstream in("sortaret.in");
int n, m;
in >> n >> m;
arce.reserve(n+1);
int x, y;
vector<int> grad_in(n+1, 0);
for (int i = 0; i < m; ++i) {
in >> x >> y;
arce[x].push_back(y);
++grad_in[y];
}
topsort(grad_in, n);
}