Pagini recente » Cod sursa (job #2474579) | Cod sursa (job #2003930) | Cod sursa (job #736054) | Utilizatori inregistrati la Grigore Moisil 2009, clasa a 9a | Cod sursa (job #1434042)
#include <iostream>
#include <fstream>
#include <vector>
//#define pb push_back
using namespace std;
const char iname[] = "sortaret.in";
const char oname[] = "sortaret.out";
const int NMAX = 50100;
vector<int> g[NMAX];
vector<int> c[NMAX];
int q[NMAX], deg[NMAX];
int n, m;
void read()
{
ifstream f(iname);
f>>n>>m;
for(int i = 0; i < m; i++)
{
int x, y;
f>>x>>y;
g[x].push_back(y);
//c[x].push_back(cost);
deg[y]++;
}
}
void write()
{
ofstream g(oname);
for(int i = 1; i <= q[0]; i++)
g<<q[i]<<' ';
}
void sort_topologically()
{
vector<int> :: iterator it;
for(int i = 1; i <= n; i++)
if(deg[i] == 0)
q[++q[0]] = i;
for(int i = 1; i <= n; i++)
{
int x = q[i];
for(it = g[x].begin(); it != g[x].end(); ++it)
{
deg[*it]--;
if(deg[*it] == 0)
q[++q[0]] = *it;
}
}
}
int main()
{
read();
sort_topologically();
write();
return 0;
}