Pagini recente » Atasamentele paginii Profil dragossofia | Cod sursa (job #517841) | Monitorul de evaluare | Cod sursa (job #1369345) | Cod sursa (job #1010550)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 50100
#define pb push_back
#define fr(i,a,b) for(int i=a;i<=b;++i)
int n,m,deg[MAXN],Q[MAXN];
vector<int> g[MAXN];
// deg[x] = gradul exterior al nodului x
// folosesc o coada Q in care introduc pe rand nodurile care
// au gradul exterior zero
// complexitate O(N+M)
void topsort()
{
vector<int>::iterator it;
fr(i,1,n)
if(deg[i]==0) Q[++Q[0]]=i;
fr(i,1,n)
{
int x=Q[i];
for(it=g[x].begin();it!=g[x].end();++it)
{
deg[*it]--;
if(deg[*it]==0) Q[++Q[0]]=*it;
}
}
}
void be()
{
int i,a,b;
scanf("%d %d\n",&n,&m);
fr(i,1,m)
{
scanf("%d %d\n", &a, &b);
g[a].pb(b);
deg[b]++;
}
}
void ki()
{
fr(i,1,n)
printf("%d ",Q[i]);
}
int main(void)
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
be();
topsort();
ki();
return 0;
}