Pagini recente » Cod sursa (job #651242) | Cod sursa (job #1456948) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2907429)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
#define MAX 100001
int N,M,x,y,i;
vector <int> A[MAX], Q;
int grad[MAX];
void citire()
{
f >> N >> M;
for (i = 1; i <= M; i++)
{
f >> x >> y;
A[x].push_back(y);
grad[y]++;
}
for (i = 1; i <= N; i++)
cout<<grad[i]<<" ";
f.close();
}
void sortare_topologica()
{
for (i=1; i<=N; i++)
if (grad[i] == 0)
Q.push_back(i);
for (i=0; i<N; i++) {
x = Q[i];
for (auto j: A[x]) {
grad[j]--;
if (grad[j] == 0)
Q.push_back(j);
}
}
}
int main()
{
// folosesc liste de vecini pentru retinerea grafului
citire();
sortare_topologica();
for (i=0; i<N; i++)
g<<Q[i]<<" ";
g.close();
return 0;
}