Pagini recente » Istoria paginii runda/lab10d22mai2014 | dot-com/2012/clasament/runda-1 | Cod sursa (job #2736124) | Monitorul de evaluare | Cod sursa (job #1699897)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NMax 50001
#define ALB 0
#define GRI 1
#define NEGRU 2
struct node{
int v;
struct node * next;
};
int idx;
int visit(int n, int *visited, int *result, struct node* D);
int main(void) {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w+", stdout);
int n,m;
scanf("%d %d", &n, &m);
int *visited = malloc(sizeof(int)*n);
int *R = malloc(sizeof(int)*n);
struct node *D = malloc(sizeof(struct node) * n);
for(int i = 0; i <= n; i++) {
D[i].v = i;
D[i].next = NULL;
}
memset(visited, 0, n);
memset(R, 0, n);
for(int i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
struct node *N = malloc(sizeof(struct node));
N->v = y;
N->next = D[x].next;
D[x].next = N;
}
for(int i = 1; i <= n; i++) {
visit(i, visited, R, D);
}
free(visited);
for(int i = idx; i; i--) {
printf("%d ", R[i]);
}
printf("\n");
free(R);
return 0;
}
int visit(int n, int *visited, int *result, struct node *D) {
if(visited[n] == NEGRU) return 0;
if(visited[n] == GRI) {
printf("**** cycle detected **** \n");
return -1;
}
visited[n] = GRI;
struct node *p = D[n].next;
while(p) {
int k = p->v;
if(visited[k] == ALB)
visit(k, visited, result, D);
p = p->next;
}
visited[n] = NEGRU;
result[++idx] = n;
return 0;
}