Pagini recente » Cod sursa (job #3367552) | Atasamentele paginii Profil mihai.ortelecan | Cod sursa (job #3366077) | Cod sursa (job #3366092) | Cod sursa (job #3366168)
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int N = 100010;
int n,m,gi[N],s[N],t=0,b=1; /// t=top=unde am adaugat ultimul nod in sirul sortat b=bottom= de unde iau urmatorul nod neprocesat
vector<int> v[N];
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
v[x].push_back(y);
gi[y]++;
}
for(int i=1;i<=n;i++)
if(gi[i]==0)
{
t++;
s[t]=i;
}
while(t<n) /// cat timp nu am pus toate cele n noduri
{
int nod=s[b]; /// alege ultimul nod neprocesat dar care a ajuns in sir
b++; /// trec la urmatorul nod care va fi procesat in viitor
for(auto vec:v[nod])
{
gi[vec]--;/// scade o unitate din gradul interior al fiecarui vecin
if(gi[vec]==0)/// daca un vecin ajunge la grad de intrare 0 se aduga in sirul de noduri sortat topologic
{
t++;
s[t]=vec;
}
}
}
/// afisam sirul de noduri sortat topologic
for(int i=1;i<=n;i++)
g<<s[i]<<' ';
g<<'\n';
return 0;
}