Pagini recente » Cod sursa (job #691769) | Cod sursa (job #1979403) | Cod sursa (job #402369) | Cod sursa (job #1388207) | Cod sursa (job #976685)
Cod sursa(job #976685)
#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;
}