zimbabue

#include <stdio.h>
#include <stdlib.h>
#define MAXVERTICES 100
#define MAXARESTAS  400
int caminhos = 0;


typedef struct
{
    int Adj[MAXVERTICES][MAXVERTICES];
    int Inc[MAXVERTICES][MAXARESTAS];
    int NVertices;
    int NArestas;
    int visitado[MAXVERTICES];
} TGrafo1;

struct elementoFila
{
    int num;
    struct fila *prox;
};
typedef struct elementoFila eFila;

struct tipofila
{
    eFila *primeiro;
    int tamanho;
};
typedef struct tipofila tFila;

void zeraFila(tFila *F)
{
    F->primeiro = NULL;
    F->tamanho = 0;
    return;
}

void addFila(tFila *F, int num)
{
    if(F->tamanho != 0)
    {
        eFila *eAux;
        eAux = F->primeiro;
        while (eAux->prox != NULL)
        {
            eAux = eAux->prox;
        }
        eFila *eNovo;
        eNovo = (eFila*) malloc (sizeof(eFila));
        eAux->prox = eNovo;
        eNovo->num = num;
        F->tamanho++;
        eNovo->prox = NULL;
        return;
    }
    else if(F->tamanho == 0)
    {
        eFila *eNovo;
        eNovo = (eFila*) malloc (sizeof(eFila));
        F->primeiro = eNovo;
        eNovo->num = num;
        F->tamanho++;
        eNovo->prox = NULL;
        return;
    }

    return;
}

void removeFila(tFila *F)
{
    if(F->tamanho != 0)
    {
        eFila *eAux;
        eAux = F->primeiro;
        F->primeiro = eAux->prox;
        free(eAux);
        F->tamanho--;
    }
    return;
}

void insere_aresta(TGrafo1* A, int V1, int V2){
                A->Adj[V1][V2] = 1;
}

void inicializa(TGrafo1* A){
    int j;
    int i;
        for(j = 0; j < A->NVertices + 1; j++)
        {
            A->visitado[j] = 0;
        }
}

void bsf(TGrafo1 *A, int inicio, int fim)
{
    int i;
    int j;
    int auxn;
    tFila fila;
    zeraFila(&fila);
    addFila(&fila, inicio);
    A->visitado[inicio] = 1;

    do
    {
        auxn = fila.primeiro->num;

        for(i = 0; i < A->NVertices + 1; i++)
        {

            if(A->Adj[auxn][i] == 1 && A->visitado[i] != 1 && i != fim && i != inicio)
            {
                A->visitado[i] = 1;
                addFila(&fila,i);
            }

            if(A->Adj[auxn][i] == 1 && i == fim)
            {
                //printf("Caminho\n");
                caminhos++;
            }
        }
        removeFila(&fila);
    }while(fila.tamanho != 0);
    return;
}

int main(){
    int rooms = 0;
    int paths = 0;
    int aux1 = -1;
    int aux2 = -1;
    int i;
    TGrafo1 Mazeotaur;

    do{
        scanf("%d %d", &rooms, &paths);
    }while(rooms < 1 || paths < 1);

    Mazeotaur.NArestas = paths;
    Mazeotaur.NVertices = rooms;

    inicializa(&Mazeotaur);

    for(i = 0; i < paths; i++)
    {
        do
        {
            scanf("%d %d", &aux1, &aux2);
        }while(aux1 < 0 || aux2 < 0);

        insere_aresta(&Mazeotaur, aux1, aux2);
    }

    scanf("%d %d", &aux1, &aux2); //Inicio e Fim

    bsf(&Mazeotaur, aux1, aux2);
    printf("%d\n", caminhos);

    return 0;
}