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

typedef struct aresta{
	struct vertice *vert;
	struct aresta *prox;
} Aresta;

typedef struct vertice{
	char info;
	struct aresta *adjacentes;
	struct vertice *prox;
} Vertice;

Vertice* InsereVertice(Vertice *lista, char c)
{
	Vertice *vert = (Vertice*)malloc(sizeof(Vertice));
	vert->info = c;
	vert->adjacentes = NULL;
	vert->prox = lista;
	return vert;
}

Aresta* InsereAdjacencia(Vertice *origem, Vertice *destino)
{
	Aresta *ar = (Aresta*)malloc(sizeof(Aresta));
	ar->vert = destino;
	ar->prox = origem->adjacentes;
	return ar;
}

Vertice* BuscaVertice(Vertice *lista, char c)
{
	Vertice *p;
	for (p = lista; p != NULL; p = p->prox)
	{
		if (p->info == c)
			return p;
	}
	return NULL;
}

int main()
{
	Vertice *listaVertices = NULL;
	Aresta *p, *t;
	Vertice *vert1, *vert2;
	int i;

	listaVertices = InsereVertice(listaVertices, 'u');
	listaVertices = InsereVertice(listaVertices, 'v');
	listaVertices = InsereVertice(listaVertices, 'w');
	listaVertices = InsereVertice(listaVertices, 'x');
	listaVertices = InsereVertice(listaVertices, 'y');
	listaVertices = InsereVertice(listaVertices, 'z');
	
	vert1 = BuscaVertice(listaVertices, 'u');
	vert2 = BuscaVertice(listaVertices, 'v');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert2 = BuscaVertice(listaVertices, 'x');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert1 = BuscaVertice(listaVertices, 'v');
	vert2 = BuscaVertice(listaVertices, 'y');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert1 = BuscaVertice(listaVertices, 'x');
	vert2->adjacentes = InsereAdjacencia(vert2, vert1);
	vert2 = BuscaVertice(listaVertices, 'v');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert1 = BuscaVertice(listaVertices, 'w');
	vert2 = BuscaVertice(listaVertices, 'y');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert2 = BuscaVertice(listaVertices, 'z');
	vert1->adjacentes = InsereAdjacencia(vert1, vert2);
	vert2->adjacentes = InsereAdjacencia(vert2, vert2);
	
	for (vert1 = listaVertices; vert1 != NULL; vert1 = vert1->prox)
	{
		printf("%c -> ", vert1->info);
		for (p = vert1->adjacentes; p != NULL; p = p->prox)
		{
			if (p->prox != NULL)
				printf("%c -> ", p->vert->info);
			else 
				printf("%c", p->vert->info);
		}
		printf("\n");
	}
	
	vert1 = listaVertices;
	while(vert1 != NULL)
	{
		vert2 = vert1->prox;
		p = vert1->adjacentes;
		while(p != NULL)
		{
			t = p->prox;
			free(p);
			p = t;
		}
		free(vert1);
		vert1 = vert2;
	}	
}