Pagini recente » Cod sursa (job #2892804) | Cod sursa (job #373400) | Cod sursa (job #1421528) | Cod sursa (job #2641845) | Cod sursa (job #2787366)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
vector<vector<int>> la; //vector in care retinem listele de adiacenta pentru fiecare nod
queue<int> q; //coada folosita la sortarea topologica
vector<int> gr_int; //vector in care retinem gradele interioare ale nodurilor
int main()
{
//citim datele si completam listele de adiacenta si vectorul de grade
fin>>n>>m;
la.resize(n+1);
gr_int.resize(n+1);
for(int i=0; i<m; ++i)
{
int x ,y;
fin >> x >> y;
la[x].push_back(y);
++gr_int[y];
}
//parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
for(int i=1; i<=n; ++i)
if(gr_int[i]==0)
q.push(i);
//parcurgem coada pentru a obtine o sortare topologica
while(!q.empty())
{
int x;
//extragem un nod din coada
x = q.front();
q.pop();
//scadeam gradele interioare ale nodurilor in care intra nodul curent
for(int i=0; i<la[x].size(); ++i)
{
int y = la[x][i];
--gr_int[y];
if(gr_int[y] == 0)
q.push(y);
}
fout << x << " ";
}
return 0;
}