Pagini recente » Cod sursa (job #2259999) | Cod sursa (job #327132) | Borderou de evaluare (job #2121569) | Cod sursa (job #2421835) | Cod sursa (job #3269818)
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
vector<set<int>> la;
vector<int> sortare_topologica, grad_intern;
void Read()
{
f >> n >> m;
la.resize(n + 1);
grad_intern.resize(n + 1, 0);
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
la[x].insert(y);
grad_intern[y]++;
}
}
void sorteaza_topoligic(vector<set<int>> &la, vector<int> &sortare_topologica, vector<int> &grad_intern)
{
queue<int> coada;
for (int i = 1; i <= n; i++)
if (grad_intern[i] == 0)
coada.push(i);
while (!coada.empty())
{
int nod = coada.front();
coada.pop();
for (auto &vecin : la[nod])
{
grad_intern[vecin]--;
if (grad_intern[vecin] == 0)
coada.push(vecin);
}
sortare_topologica.push_back(nod);
}
}
int main()
{
Read();
sorteaza_topoligic(la, sortare_topologica, grad_intern);
for (auto &nod : sortare_topologica)
{
g << nod << ' ';
}
return 0;
}