Pagini recente » Cod sursa (job #1203069) | Cod sursa (job #736783) | Cod sursa (job #1372773) | Cod sursa (job #782295) | Cod sursa (job #1480627)
#include <fstream>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
#define MAXN 50100
int N, M, grad_ext[MAXN], Q[MAXN]; vector<int> L[MAXN];
// deg[x] = gradul exterior al nodului x
// folosesc o coada Q in care introduc pe rand nodurile care
// au gradul exterior zero
// complexitate O(N+M)
void Citire()
{
int i, x, y;
fin >> N >> M;
for(i = 1; i <= M; i++)
{ fin >> x >> y; /// citesc noduri
L[x].push_back(y); // actualizez lista de adiacenta
grad_ext[y]++; // cresc gradul exterior al nodului b
}
}
void Rezolva()
{
int i, x,y;
vector<int>::iterator it;
int k=0;
for (x = 1; x <= N; x++)
if(grad_ext[x] == 0) Q[++k] = x;
for(i = 1; i <= N; i++)
{
x = Q[i];
for(it = L[x].begin(); it != L[x].end(); ++it)
{
grad_ext[*it]--;
if(grad_ext[*it] == 0) Q[++k] = *it;
}
}
}
void Afisare()
{
for(int i = 1; i <= N; i++)
fout << Q[i] << " ";
fout << endl;
}
int main()
{
Citire();
Rezolva();
Afisare();
return 0;
}