Pagini recente » Cod sursa (job #1111300) | Cod sursa (job #1347184) | Cod sursa (job #662901) | Cod sursa (job #922520) | Cod sursa (job #1427109)
#include <fstream>
#include <list>
using namespace std;
ifstream f1("sortaret.in");
ofstream f2("sortaret.out");
#define MX 50010
int n,m, c[MX], k, nr_servant[MX], sol[MX];
list<int> master[MX];
int main()
{
int i, x, y;
f1>>n>>m; // we have n people and m relations between them
for (i=1; i<= m; i++)
{
f1>>x>>y; // x is the master of y
master[y].push_back(x); // be my servant y !
nr_servant[x]++; // i have more servants now ! Muahaha
}
for (i=1; i<=n; i++) // we shall kill the servants first, so put them on the black list
if ( nr_servant[i] == 0 )
c[++k]= i;
int p=n;
while (k)
{
sol[p--]= c[1]; // put the sevant on the killing list
for (list<int>::iterator it= master[ c[1] ].begin(); it!= master[ c[1] ].end(); ++it )
{ // for every master he has
nr_servant[ *it ]--; // let the master know that he's dead
if ( nr_servant[ *it ] == 0 ) // it the master has no servants then he is a servant
c[++k]= *it; // put him on the killing list
}
c[1]= c[k--]; // the last will be the first
}
for (i=1; i<=n; i++) // now this is the killing order in which masters die first
f2<<sol[i]<<" ";
f2.close();
return 0; // obey me world !
}