Pagini recente » Cod sursa (job #2428561) | tema | Cod sursa (job #1458681) | Cod sursa (job #499539) | Cod sursa (job #2133796)
#include <iostream>
#include <fstream>
#include <queue>
#include<set>
//#define DEPANARE
using namespace std;
#define MAXN 50000
int n, m;
typedef queue<unsigned short int> CoadaDeIntregi;
typedef set<unsigned short int> Multime;
CoadaDeIntregi cSortata;
typedef CoadaDeIntregi CoziDeIntregi[MAXN+1];
CoziDeIntregi succesori;
unsigned short int gradIntrare[MAXN+1];
Multime noduriDeGradInterior0;
void citire(void)
{
ifstream fin("sortaret.in", ios::in);
fin>>n>>m;
unsigned short int i,x,y;
for(i=1;i<=n;i++)
{
noduriDeGradInterior0.insert(i); //presupunem ca toate elementele ar fi de grad 0
}
for(i=0;i<m;i++)
{
fin>>x>>y;
gradIntrare[y]++;
succesori[x].push(y);
noduriDeGradInterior0.erase(y);
}
fin.close();
}
void calcul(void)
{
unsigned short int x=0, y=0;
while(!noduriDeGradInterior0.empty())
{
x= *(noduriDeGradInterior0.begin());
noduriDeGradInterior0.erase(x);
cSortata.push(x);
while(!succesori[x].empty())
{
y=succesori[x].front();
succesori[x].pop();
if( ! (--gradIntrare[y]) ) //a ajuns 0?
{
noduriDeGradInterior0.insert(y);
}
}
}
}
void scrieSolutia(void)
{
ofstream fout("sortaret.out", ios::out);
while(!cSortata.empty())
{
fout<<cSortata.front()<<" ";
cSortata.pop();
}
fout<<endl;
fout.close();
}
int main()
{
bool vecheaValoare=cin.sync_with_stdio(false);
citire();
#ifdef DEPANARE
cout<<sizeof(cSortata)<<endl;
cout<<sizeof(succesori)<<endl;
cout<<sizeof(gradIntrare)<<endl;
cout<<sizeof(noduriDeGradInterior0)<<endl;
#endif
//cout<<"multimea de succesori ocupa"<<sizeof(succesori)<<endl;
//cout<<sizeof(queue<int>)<<endl;
calcul();
//cout<<sizeof(cSortata)<<endl;
scrieSolutia();
cin.sync_with_stdio(vecheaValoare);
return 0;
}