Pagini recente » Cod sursa (job #868066) | Cod sursa (job #1805294) | Cod sursa (job #243466) | Cod sursa (job #1990622) | Cod sursa (job #2834492)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
//Restrictii
//1 <= N <= 100 000
//0 <= M <= minim(200 000, N * (N + 1) / 2)
//Pentru 50 % dintre teste 1 <= N <= 1 000
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<vector<int>> v;
void citire(int n, int m) {
int x, y;
v.resize(n + 1);
for (int i = 0; i < m; i++) {
f >> x >> y;
v[x].push_back(y);
}
}
void DFS(vector<bool>& vizitat, int start, stack<int>& stack) {
vizitat[start] = true;
for (int i = 0; i < v[start].size(); i++)
if (vizitat[v[start][i]] == false)
DFS(vizitat, v[start][i], stack);
stack.push(start);
}
void sortare_topologica(int n) {
vector<bool> vizitat(n + 1, false);
stack<int> stack;
for (int i = 1; i <= n; ++i) {
if (vizitat[i] == false) {
DFS(vizitat, i, stack);
}
}
for (int i = stack.size() - 1; i >= 0; i--)
{
int a = stack.top();
stack.pop();
g << a << " ";
}
}
int main() {
int n, m;
f >> n >> m;
citire(n,m);
sortare_topologica(n);//de nr de noduri
f.close();
g.close();
return 0;
}