Pagini recente » Cod sursa (job #1288623) | Cod sursa (job #600467) | Cod sursa (job #2346999) | Cod sursa (job #3259297) | Cod sursa (job #976605)
Cod sursa(job #976605)
#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;
}