Pagini recente » Monitorul de evaluare | Cod sursa (job #1719846) | Cod sursa (job #1840932) | Rating Costea Stefania (stefania_costea) | Cod sursa (job #1723807)
#include <iostream>
#include <fstream>
#include <queue>
#include <set>
using namespace std;
#define NMAX 50000
set<int> ad[NMAX + 1];
int ordine[NMAX + 1];
vector<bool> inCoada(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;
ad[x].insert(y);
inCoada[y] = true;
}
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(!inCoada[i])
{
q.push(i);
inCoada[i] = true;
}
else inCoada[i] = false;
}
int indice = 0;
while(!q.empty())
{
int nod = q.front();
q.pop();
ordine[++indice] = nod;
for(int vecin : ad[nod])
{
if(!inCoada[vecin])
{
q.push(vecin);
inCoada[vecin] = true;
}
}
}
}