Pagini recente » Cod sursa (job #3228492) | Cod sursa (job #903720) | Cod sursa (job #598810) | Cod sursa (job #1494691) | Cod sursa (job #546119)
Cod sursa(job #546119)
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define NMAX 50001
#define MMAX 10001
ifstream fin(FIN);
ofstream fout(FOUT);
int deq[NMAX], viz[NMAX],Q[NMAX];
vector<int> G[NMAX];
int n,m;
void ReadInputs()
{
int a,b;
fin >> n >> m;
for(int i = 1; i <= m; ++i){
fin >> a >> b;
G[a].push_back(b);
deq[b]++;
}
}
//n^2
void SolveN2()
{
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j){
if( !viz[j] && !deq[j] )
{
viz[j] = 1;
fout << j << " " ;
for(int k = 0; k < G[j].size(); ++k)
deq[ G[j][k] ]--;
break;
}
}
}
//O(N*M)
void Solve()
{
int x;
vector<int>::iterator it;
for(int i = 1; i <= n; ++i)
if( deq[i] == 0 ) Q[++Q[0]] = i;
for(int i = 1; i <= n; ++i){
x = Q[i];
for(it = G[x].begin(); it != G[x].end();it++)
{
deq[*it]--;
if( deq[*it] == 0 ) Q[++Q[0]] = *it;
}
}
for(int i = 1; i <= n; i++)
fout << Q[i] << " ";
}
int main()
{
ReadInputs();
//SolveN2();
Solve();
return 0;
}