#include <stdio.h>
#include <stdlib.h>

struct ponto {
    int peso;
    int valor_do_vertice;
};typedef struct ponto Ponto;

struct celula {
    struct celula* prox;
    Ponto ponto;
};typedef struct celula Celula;

struct lista {
    Celula *primeiro,*ultimo;
};typedef struct lista Lista;

struct grafo {
    Lista *adjacentes;
    int numero_de_vertices;
    int numero_de_arestas;
};typedef struct grafo Grafo;

Ponto* criaPonto (int peso, int valor_do_vertice) {
    Ponto *ponto;
    ponto->peso = peso;
    ponto->valor_do_vertice = valor_do_vertice;
    return ponto;
}

Celula* criaCelula (Ponto* ponto) {
    Celula* celula;
    celula->ponto = ponto;
    celula->prox = NULL;
}

Lista* iniciaLista () {
    Lista* lista;
    lista->primeiro = NULL;
    lista->primeiro->prox = lista->ultimo;
    lista->ultimo = lista->primeiro;
    return lista;
}

int isListaVazia (Lista* lista) {
    return lista->primeiro == NULL;
}

Lista* procuraCelula(Lista* lista, int valor_do_vertice) {
    Celula* p;
    if (lista->primeiro->prox == NULL) {
        return lista->primeiro;
    }
    else {
        p = lista->primeiro;
        while (p->ponto->valor_do_vertice != valor_do_vertice) {
            p = p->prox;
        }
        return p;
    }
}

void insereNaLista (int peso, int valor_do_vertice, Lista* lista) {
    Ponto *ponto;
    ponto = criaPonto(peso, valor_do_vertice);
    if (isLista(lista)) {
        lista->primeiro = malloc(sizeof(Celula));
        lista->primeiro = criaCelula(ponto);
        lista->ultimo = lista->primeiro;
    }
    else {
        lista->ultimo->prox = malloc(sizeof(Celula));
        lista->ultimo->prox = criaCelula(ponto);
        lista->ultimo = lista->ultimo->prox;
    }
}

Lista* excluiUltimaCelula (Lista* lista) {
    if (lista->primeiro->prox == NULL) {
        lista->primeiro = NULL;
        lista->ultimo = lista->primeiro;
        return lista;
    }
    else {
        Celula* p, q;
        p = Lista->primeiro;
        q = p->prox;
        while (q->prox != NULL) {
            p = q;
            q->prox;
        }
        free(q);
        lista->ultimo = p;
        return lista;
    }
}

void esvaziaLista (Lista* lista) {
    while (lista->primeiro != NULL) {
        excluiUltimaCelula(lista);
    }
}

Grafo* iniciaGrafo(int numero_de_vertices) {
    Grafo* grafo;
    grafo->numero_de_arestas = 0;
    grafo->numero_de_vertices = numero_de_vertices;
    if (numero_de_vertices > 0) {
        grafo->adjacentes = malloc(numero_de_vertices * sizeof(Lista));
    }
    return grafo;
}

void alocaMais(Grafo* grafo) {
    grafo->adjacentes = realloc(grafo->adjacentes, (grafo->numero_de_vertices*2)*sizeof(Lista));
}

void esvaziaGrafo(Grafo* grafo) {
    int contador;
    for (i = 0; contador < grafo->numero_de_vertices; contador++) {
        esvaziaLista(grafo->adjacentes);
    }
}

void insereAresta(int vertice1, int vertice2, int peso, Grafo* grafo) {
    insereNaLista(peso, vertice2, grafo->adjacentes[vertice1]);
}