Cod sursa(job #976685)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 23 iulie 2013 17:59:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 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 isEmpty() {
            if(pHead == NULL)
				return 1;
			return 0;
        }

};

int *col;
Deque D;

void DFS(int u, int A[NMAX][NMAX], int N){
	int v;
	col[u] = 1;
	for(v = 1; v <= N; v++)
		if(A[u][v] == 1)
			if(col[v] == 0)
				DFS(v, A, N);

	col[u] = 2;
	D.addBack(u);
	
}

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;

	col = 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;
	}
	for(int u = 1; u <= N; u++)
		if(col[u] == 0)
			DFS(u, A, N);
	
	while(!D.isEmpty())
		fprintf(pg, "%d ", D.removeFront());

	fclose(pf);
	fclose(pg);

	return 0;
}