Pagini recente » Cod sursa (job #412631) | Cod sursa (job #1197332) | Cod sursa (job #1582967) | Cod sursa (job #1086526) | Cod sursa (job #2640326)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n,m;//nr of nodes
vector<int> g[50100];
int eg[50100]={0};
int q[50100]={0};// queue that has all grades 0
ifstream f("sortaret.in");
ofstream gg("sortaret.out");
void citire_fisier(void )
{
int i,a,b;
for(i=1;i<=m;i++)
{
f>>a>>b;
g[a].push_back(b);// for every node we have as value it's thing where it goes
eg[b]++;//how many nodes does one node have
}
}
void sortare_topologica(void)
{
int i, x;
vector<int>:: iterator it;
for(x=1;x<=n;x++)
{
if(eg[x]==0)
{
q[++q[0]]=x;// introducem in listpe rand elementele
}
for(int i=1;i<=n;i++)
{
x=q[i];
for(it = g[x].begin();it!=g[x].end();++it)
{
eg[*it]--;
if(eg[*it]==0)
{
q[++q[0]]=*it; //*it to take the alue of the it
}
}
}
}
}
int main()
{
f>>n>>m;
citire_fisier();
sortare_topologica();
for(int i=1;i<=n;i++)
{
gg<<q[i]<<" ";
}
}