Pagini recente » Cod sursa (job #1407843) | Cod sursa (job #2638847) | Cod sursa (job #610713) | Cod sursa (job #527724) | Cod sursa (job #1219337)
//Sortare topologica pe graf orientat aciclic
// Sortare in care daca exista un arc ( i, j ), atunci i apare inaintea lui j in aceasta ordonare
// facem o parcurgere in latime, eliminand nodurile pe rand, daca au gradul interior 0
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int i,n,m,a,b,gradint[50005],aux;
vector<int>coada;
vector<int> v[50005];
vector<int> ::iterator itr;
void toposort()
{
for(i=1;i<=n;++i)
{
if(gradint[i]==0)
{
coada.push_back(i); // pentu ca este aciclic tot timpul va intra aici
}
}
for(i=0;i<n;++i)
{
aux=coada[i];
for(itr=v[aux].begin();itr!=v[aux].end();itr++)
{
gradint[*itr]--;
if(gradint[*itr]==0)
{
coada.push_back(*itr); // nu avem nevoie de vizitat[] pentru ca daca gradul int este 0 nu se va mai ajunge la acel nod
}
}
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>a>>b;
gradint[b]++;
v[a].push_back(b);
}
toposort();
for(i=0;i<n;++i)
fout<<coada[i]<<" ";
return 0;
}