Cod sursa(job #976605)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 23 iulie 2013 14:56:52
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include<stdio.h>
#include<stdlib.h>
#define NMAX 100

struct Elem{
	int value;
	struct Elem *prev, *next;
};

class Deque{
	public:
		struct Elem *pHead, *pTail;		

		Deque(){
			pHead = NULL;
			pTail = NULL;
		}

		~Deque(){}

		void addBack(int info) {
            struct Elem *paux;

            paux = new struct Elem;
            paux->value = info;
            paux->prev = pTail;
            paux->next = NULL;

            if (pTail != NULL) 
				pTail->next = paux;
            pTail = paux;
            if (pHead == NULL) 
				pHead = pTail;
        }

		int removeFront() {
            struct Elem *paux;
			int x = pHead->value;
			
            if (pHead != NULL) {
                paux = pHead->next;
				
                if (pHead == pTail) 
					pTail = NULL;
                delete pHead;
                pHead = paux;
                if (pHead != NULL) 
					pHead->prev = NULL; 
				return x;
            }
            else{
				int x;
				fprintf(stderr, "Error - The deque is empty!\n"); 
				return x;
			}
		}

		int removeBack() {
            struct Elem *paux;
			int x = pTail->value;

            if (pTail != NULL) {
                paux = pTail->prev;
                if (pHead == pTail) 
					pHead = NULL;
                delete pTail;
                pTail = paux;
                if (pTail != NULL) 
					pTail->next = NULL;

				return x;
            }
            else{
				int x; 
				fprintf(stderr, "Error - The deque is empty!\n");
				return x;
			}
        }

		int isEmpty() {
            if(pHead == NULL)
				return 1;
			return 0;
        }
};

int *degree;

Deque TopoS(int A[NMAX][NMAX], int N){
	Deque Dl, Dg;
	int v;

	for(v = 1; v <= N; v++)	
		if(degree[v] == 0)
			Dl.addBack(v);

	while(!Dl.isEmpty()){
		int u = Dl.removeFront();
		Dg.addBack(u);
		for(v = 1; v <= N; v++)
			if(A[u][v] == 1){
				degree[v]--;
				if(degree[v] == 0)
					Dl.addBack(v);
			}
	}
	return Dg;
}

int main(){
	int X, Y, N, M;
	FILE *pf, *pg;
	pf = fopen("sortaret.in", "r");
	pg = fopen("sortaret.out", "w");
	int A[NMAX][NMAX], i, j;

	degree = new int[NMAX];	
	fscanf(pf, "%d %d", &N, &M);

	for(i = 1; i <= N; i++)
		for(j = 1; j <= N; j++)
			A[i][j] = 0;

	for(i = 1; i <= M; i++){
		fscanf(pf, "%d %d", &X, &Y);
		A[X][Y] = 1;
		degree[Y]++;
	}

	Deque D;
	D = TopoS(A, N);

	while(!D.isEmpty())
		fprintf(pg, "%d ", D.removeFront());

	fclose(pf);
	fclose(pg);

	return 0;
}