Pagini recente » Cod sursa (job #409145) | Cod sursa (job #1497686) | Cod sursa (job #1295569) | Cod sursa (job #2256751) | Cod sursa (job #772170)
Cod sursa(job #772170)
/* sortare topologica */
#include<fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m,i,j,queue[50001],viz[50001],end,beg;
int incoming[50001];
struct edge{int node; edge* next;};
edge* a[100001];
void add(int x, int y)
{edge* q=new edge;
q->node=y;
q->next=a[x];
a[x]=q;}
//struct lista{int nod; lista* next};
//lista* head;
int main()
{f>>n>>m;
int x,y;
for(i=1; i<=m; i++)
{f>>x>>y;
add(x,y);
incoming[y]++;}
end=0;
for(i=1; i<=n; i++)
if(incoming[i]==0)
{end++;
queue[end]=i;
viz[i]=1;}
beg=1;
while(end<=n-1)
{edge* q = a[beg];
while(q)
if(viz[q->node]==0)
{incoming[q->node]--;
if(incoming[q->node]==0)
{end++;
queue[end]=q->node;
viz[q->node]=1;}
q=q->next;
}
beg++;}
for(i=1; i<=end; i++)
g<<queue[i]<<" ";
f.close();
g.close();
return 0;}