Cod sursa(job #759091)

Utilizator aranhilChivu Stefan Iulian aranhil Data 16 iunie 2012 17:25:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#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;
}