Pagini recente » Cod sursa (job #339047) | Cod sursa (job #1723820)
#include <iostream>
#include <fstream>
#include <queue>
#include <set>
using namespace std;
#define NMAX 50000
set<int> ad[NMAX + 1];
int ordine[NMAX + 1];
int gradExterior[NMAX + 1];
void sortareTopologica(int n);
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
while(m--)
{
int x, y;
fin >> x >> y;
if(ad[x].find(y) == ad[x].end())
++gradExterior[y];
ad[x].insert(y);
}
sortareTopologica(n);
for(int i = 1; i <= n; ++i)
fout << ordine[i] << " ";
return 0;
}
void sortareTopologica(int n)
{
queue<int> q;
for(int i = 1; i <= n; ++i)
{
if(gradExterior[i] == 0)
q.push(i);
}
int indice = 0;
while(!q.empty())
{
int nod = q.front();
q.pop();
ordine[++indice] = nod;
for(int vecin : ad[nod])
{
if(gradExterior[vecin] == 1)
q.push(vecin);
--gradExterior[vecin];
}
}
}