Pagini recente » Cod sursa (job #3137420) | Cod sursa (job #1010101) | Cod sursa (job #2672878) | Cod sursa (job #168523) | Cod sursa (job #759091)
Cod sursa(job #759091)
#include <stdio.h>
struct nod {
nod *next;
int x;
};
struct lista {
nod *first, *last;
lista() {
first = NULL;
last = NULL;
}
void add(int x) {
nod *nou = new nod;
nou->x = x;
nou->next = NULL;
if(last != NULL) last->next = nou;
last = nou;
if(first == NULL) first = last;
}
};
int main() {
FILE *f = fopen("sortaret.in", "r"), *g = fopen("sortaret.out", "w");
int n, m;
fscanf(f, "%d %d", &n, &m);
lista *liste = new lista[n];
lista st;
int *grad_extern = new int[n];
bool **exista = new bool*[n];
for(int i = 0; i < n; i++) {
exista[i] = new bool[n];
for(int j = 0; j < n; j++)
exista[i][j] = false;
}
for(int i = 0; i < n; i++) grad_extern[i] = 0;
for(int i = 0; i < m; i++) {
int k, l;
fscanf(f, "%d %d", &k, &l);
if(!exista[k - 1][l - 1]) {
liste[k - 1].add(l - 1);
grad_extern[l - 1] ++;
exista[k - 1][l - 1] = true;
}
}
// for(int i = 0; i < n; i++) {
// fprintf(g, "%d: ", i);
// for(nod *j = liste[i].first; j != NULL; j = j->next) {
// fprintf(g, "%d - %d; ", j->x, grad_extern[j->x]);
// }
// fprintf(g, "\n");
// }
for(int i = 0; i < n; i++) {
if(grad_extern[i] == 0) {
st.add(i);
fprintf(g, "%d ", i + 1);
}
else grad_extern[i] = 1;
}
nod *contor = st.first;
while(contor != NULL) {
nod *c2 = liste[contor->x].first;
while(c2 != NULL) {
if(grad_extern[c2->x] && exista[contor->x][c2->x]) {
st.add(c2->x);
fprintf(g, "%d ", c2->x + 1);
grad_extern[c2->x] = 0;
exista[contor->x][c2->x] = false;
}
c2 = c2->next;
}
contor = contor->next;
}
fclose(f);
fclose(g);
return 0;
}