Pagini recente » Cod sursa (job #2404494) | Cod sursa (job #215439) | Cod sursa (job #156826) | Cod sursa (job #2502107) | Cod sursa (job #780698)
Cod sursa(job #780698)
#include <fstream>
#include <vector>
using namespace std;
#define max 50001
int N, M, i, contor, n1, n2, grad[max], coada[max] ;
vector <int> Muchii[max];
void read()
{
ifstream fin("sortaret.in");
fin>>N>>M;
for(i=1;i<=M;++i)
{
fin>>n1>>n2;
Muchii[n1].push_back(n2); // pun muchiile pe care le face n1 cu alte noduri
++grad[n2]; // cresc gradul lui n2 ( ca sa-l compar cu 0 dupa iteratii )
}
}
void write()
{
ofstream fout("sortaret.out");
for(i=1;i<=N;++i)
fout<<coada[i]<<" ";
fout<<"\n";
}
void solve()
{
vector<int>::iterator it;
for(i=1;i<=N;++i)
if(grad[i]==0)
coada[++contor]=i; //bag toate nodurile care eu la inceput gradul 0
//parcurg coada si elimin muchiile pe care le formeaza nodurile cu gradul 0; scad gradul nodurilor in care intrau muchiile; daca ajung 0 le bag in coada
int aux;
for(i=1;i<=N;++i)
{
aux = coada[i];
for( it = Muchii[aux].begin() ; it != Muchii[aux].end() ; ++it )
{
--grad[*it];
if( grad[*it] == 0 )
coada[++contor] = *it ;
}
}
}
int main()
{
read();
solve();
write();
return 0;
}