Pagini recente » Cod sursa (job #422904) | Cod sursa (job #405221) | Cod sursa (job #1908639) | Cod sursa (job #111695) | Cod sursa (job #2368335)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int N_MAX = 50000;
const int M_MAX = 100000;
int N, M;
struct nod
{
int info;
nod *urm;
};
nod *v[100001];
int Q[N_MAX + 1], u; ///Coada
int gr[N_MAX + 1];
void add(int x, int y)
{
nod *p = new nod;
p->info = y;
p->urm = v[x];
v[x] = p;
}
void sortaret()
{
///Punem la inceput nodurile care au gradul exterior 0
for(int i = 1; i <= N; ++i)
if(gr[i] == 0)
Q[++u] = i;
for(int i = 1; i <= N; ++i)
{
int x = Q[i];
///Scoatem arcele care pleaca din x si adaugam
///eventual nodurile cu gradul exterior 0
for(nod *p = v[x]; p != NULL; p = p->urm)
{
int y = p->info;
gr[y]--;
if(gr[y] == 0)
Q[++u] = y;
}
}
}
void citire()
{
int x, y;
f >> N >> M;
for(int i = 1; i <= M; i++)
{
f >> x >> y;
add(x, y);
gr[y]++;
}
}
int main()
{
citire();
sortaret();
for(int i = 1; i <= N; ++i)
g << Q[i] << ' ';
return 0;
}