Mai intai trebuie sa te autentifici.
Cod sursa(job #1217064)
Utilizator | Data | 6 august 2014 15:57:45 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.16 kb |
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
const int max_n = 50004;
queue <int> q;
vector <int> a[max_n];
int i,n,m,x,y,sol[max_n],nr;
int grad_interior[max_n];
void sortare_topologica(vector <int> a[max_n], int n, int sol[max_n]){
int i,nr=0;
for(i=1;i<=n;i++)
if(!grad_interior[i]) q.push(i);
while(q.size())
{
int nod=q.front();
sol[++nr]=nod;
while(a[nod].size())
{
int vecin=a[nod].back();
grad_interior[vecin]--;
if(!grad_interior[vecin]) q.push(vecin);
a[nod].pop_back();
}
q.pop();
}
}
int main(){
fi>>n>>m;
for(i=1;i<=m;i++){
fi>>x>>y;
a[x].push_back(y);
grad_interior[y]++;
}
sortare_topologica(a,n,sol);
for(i=1;i<=n;i++) fo<<sol[i]<<" ";
fi.close();
fo.close();
return 0;
}