Pagini recente » Cod sursa (job #1543956) | Cod sursa (job #1012471) | Cod sursa (job #3126541) | Cod sursa (job #1184162) | Cod sursa (job #375144)
Cod sursa(job #375144)
//sortare topologica v1
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
#define NM 50005
#define PB push_back
#define MKP make_pair
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)
vector<int> G[NM];
set<pair<int,int> > H;
set<pair<int,int> >::iterator it;
int GI[NM],N,M;
int main()
{
int a,b;
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d %d",&N,&M);
FOR(i,1,M)
{
scanf("%d %d",&a,&b);
G[a].PB(b);
++GI[b];
}
FOR(i,1,N)
H.insert(MKP(GI[i],i));
while(!H.empty())
{
it=H.begin();
int nod=it->second;
H.erase(it);
printf("%d ",nod);
int sz=G[nod].size();
FOR(i,0,sz-1)
{
int nnod=G[nod][i];
it=H.find(MKP(GI[nnod],nnod));
H.erase(it);
--GI[nnod];
H.insert(MKP(GI[nnod],nnod));
}
}
return 0;
}