Pagini recente » Algoritmiada 2015 - Clasament Runda 1, Seniori | Cod sursa (job #2362574) | Cod sursa (job #1308097) | Cod sursa (job #1489643) | Cod sursa (job #1592949)
#include <stdio.h> /* sortarea topologica: un graf orientat fara cicluri se poate sorta topologic -
#include <stdlib.h> numarul de ordine al fiecarui nod trebuie sa fie mai mare decat numerele de
ordine ale parintilor(daca muchia (u,v) apartine grafului u trebuie sa apara
in sortare inaintea lui v */
#define NMAX 50005
int n, m, t;
int viz[NMAX];
struct node {
int inf;
struct node *pnext;
}*v[NMAX];
struct node *h; /* *h este variabila globala */
void push(int x) {
struct node *p;
p = new node;
p->inf = x;
p->pnext = h;
h = p;
}
node* inserare_inceput(node* p,int x){
node* elem=new node;
elem->inf=x;
elem->pnext=p;
return elem;
}
void DFS(int x){
if(viz[x]==0){
viz[x]=++t;
node *parcurg=v[x];
while(parcurg){
DFS(parcurg->inf);
parcurg=parcurg->pnext;
}
push(x);
}
}
int main() {
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
int i, j, k;
struct node *pc;
scanf("%d", &n);
scanf("%d", &m);
for (k = m; k >= 1; k--) {
scanf("%d%d", &i, &j);
v[i]=inserare_inceput(v[i],j);
}
h = NULL;
t = 1;
for (i = 1; i <= n; i++) {
if (viz[i] == 0) {
DFS(i);
}
}
pc = h;
while (pc != NULL) {
printf("%d ", pc->inf);
pc = pc->pnext;
}
printf("\n");
return 0;
}