Mai intai trebuie sa te autentifici.
Cod sursa(job #2627768)
Utilizator | Data | 12 iunie 2020 14:18:13 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 60 |
Compilator | c-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.58 kb |
#include <stdio.h>
#include <stdlib.h>
#define mare 50003
typedef struct {
int a[mare];
int size;
} Queue;
typedef struct {
int edge[mare];
int size;
} List;
int dequeue(Queue *q) {
int elem;
if(q -> size != 0)
elem = q -> a[0];
else
elem = 0;
for(int i = 0; i < q -> size; i++) {
q -> a[i] = q -> a[i + 1];
}
q -> size--;
return elem;
}
void enqueue(Queue *q, int elem) {
q -> a[q -> size] = elem;
q -> size++;
}
int ind[mare];
List *list;
int main()
{
int n, m;
FILE *fin, *fout;
fin = fopen("sortaret.in", "r");
fout = fopen("sortaret.out", "w");
if(!fin || !fout)
printf("nope");
fscanf(fin, "%d %d", &n, &m);
Queue q;
q.size = 0;
list = (List *) calloc(n + 3, sizeof(List));
for(int i = 0; i < m; i++) {
int x, y;
fscanf(fin, "%d %d", &x, &y);
ind[y]++;
list[x].edge[list[x].size++] = y;
}
for(int i = 1; i <= n; i++) {
if(ind[i] == 0) {
enqueue(&q, i);
ind[i] = -1;
}
}
while(q.size != 0) {
int node = dequeue(&q);
fprintf(fout, "%d ", node);
for(int j = 0; j < list[node].size; j++) {
ind[list[node].edge[j]]--;
}
for(int x = 1; x <= n; x++) {
if(ind[x] == 0) {
enqueue(&q, x);
ind[x] = -1;
}
}
}
fclose(fin);
fclose(fout);
return 0;
}