Cod sursa(job #1229145)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 16 septembrie 2014 17:17:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <algorithm>
#define max_n 50000
#define u_i unsigned int
#include <queue>

using namespace std;

struct node{
u_i inf;
node *next;
} *G[max_n];
u_i n,x,y;
long m,d[max_n];
bool vis[max_n];
queue <u_i> S,L;

void add_node(unsigned int x,unsigned int y){
node *c=new node;
c->inf=y;
c->next=G[x];
G[x]=c;
d[y]++;
}

int main(void){
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d%d",&n,&m);
while(m-- ){
scanf("%d%d",&x,&y);
add_node(x,y);
}
for(x=1;x<=n;x++)
  if(!d[x])
     S.push(x);
while(!S.empty()){
x=S.front();
S.pop();
L.push(x);
while(G[x]){
//d[G[x]->inf]--;
if(--d[G[x]->inf])
S.push(G[x]->inf);
G[x]=G[x]->next;
}
}
while(!L.empty()){
printf("%d ",L.front());
L.pop();
}
}