Pagini recente » Monitorul de evaluare | Cod sursa (job #1658064) | Monitorul de evaluare | Cod sursa (job #1658065) | Cod sursa (job #1658063)
#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 D[NMax][NMax] = {{0}}; */
/* int R[NMax] = {0}; */
/* int visited[NMax] = {0}; */
int idx;
int visit(int n, int *visited, int *result, struct node* D);
void print_list(struct node* D, int n){
for(int i = 1; i <= n; i++) {
printf("[%d] ", i);
struct node *p = &D[i];
while(p) {
printf("%d ", p->v);
p = p->next;
}
printf("\n");
}
}
/* void print_matrix(int n) { */
/* for(int i = 1; i < n; i++) { */
/* for(int j = 1; j < n; j++) { */
/* printf("%d ", D[i][j]); */
/* } */
/* printf("\n"); */
/* } */
/* } */
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 *D1 = malloc(sizeof(struct node) * n);
for(int i = 0; i < n; i++) {
D1[i].v = i;
D1[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);
/* D[x][y] = 1; */
struct node *N = malloc(sizeof(struct node));
N->v = y;
N->next = NULL;
// node* p = D1[i].next;
N->next = D1[i].next;
D1[i].next = N;
}
/* print_list(D1, n); */
/* print_matrix(n); */
for(int i = 1; i <= n; i++) {
visit(i, visited, R, D1);
}
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;
}