Pagini recente » Cod sursa (job #3233579) | Cod sursa (job #1634461) | Cod sursa (job #3138922) | Cod sursa (job #1627226) | Cod sursa (job #1109653)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int X[50004];//vectorul de parcurgere din BF
int GI[50004];//gradele interioare
vector<int> V[50004];//listele de adiacenta
int n,m;//dimensiunile grafului
void sort_top_BF()
{
int st,dr=0;
for (int i = 1; i <= n; i++)//adaug in X varfurile de pornire (grad interior 0)
if (GI[i] == 0) X[++dr] = i;
st = 1;//porneste de la primul vf din X
while (st <= dr)//cat timp mai am varfuri neparcurse
{
int v = X[st];//varful curent
for (int i = 0; i < V[v].size(); i++)//parcurg lista lui v
{
int j = V[v][i];//varful din lista lui v de la pozitia i
GI[j]--;//scad gradul lui j
if (GI[j] == 0) //daca are gradul 0 (=>toti dinaintea lui au fost parcusi)
X[++dr] = j;//il adaug si pe j in X
}
st++;//trec la urmatorul nod din stanga lui X
}
for (int i = 1; i <= n; i++)
fout<<X[i]<<" ";//afisez vectorul X
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
V[x].push_back(y);
GI[y]++;
}
sort_top_BF();
fin.close();
fout.close();
return 0;
}