/* ==========  ========== ========== ========= */
//          Adjacency List Graph Data          //
//          Structure Implementation           //
//           in C using Linked List            //
//                                             //
//         Functions follow Pascal Case        //
//           Convention and Variables          //
//         follow Camel Case Convention        //
//                                             //
//            Author - Vamsi Sangam            //
//            Theory of Programming            //
/* ========== ========== ========== ========== */
   
#include <stdio.h>
#include <stdlib.h>

// 26 Upper Case letters + 26 Lower Case letters
#define SIZE 52
   
struct Edge {
    char vertex;
    struct Edge * next;
};
  
// Inserts Node to the Linked List by Head Insertion - O(1)
// Returns address of head which is the newly created node.
struct Edge * AddEdge(struct Edge * currentHead, char newVertex)
{
    struct Edge * newHead = (struct Edge *) malloc(sizeof(struct Edge));
   
    newHead->vertex = newVertex;
    newHead->next = currentHead;
   
    return newHead;
}

// A to Z -> Are mapped from index 0 to 25
// a to Z -> Are mapped from index 26 to 51
int charToIndex(char letter)
{
	if (letter >= 'A' && letter <= 'Z') {
		return letter - 'A';
	} else {
		return letter + 26 - 'a';
	}
}

char indexToChar(int index)
{
	if (index < 26) {
		return index + 'A';
	} else {
		return index - 26 + 'a';
	}
}
  
int main()
{
    int edges, i;
    char v1, v2;
   
    printf("Enter the Number of Edges -\n");
    scanf("%d", &edges);
   	
   	// We create an adjacency matrix to accomodate
	// upper case and lower case letters
    struct Edge * adjacencyList[SIZE];
   
    // Must initialize your array
    for (i = 0; i < SIZE; ++i) {
        adjacencyList[i] = NULL;
    }
    
    getchar();	// to clear enter input
    printf("Enter the Edges (v1 --> v2)\n");
   
    for (i = 1; i <= edges; ++i) {
        scanf("%c %c", &v1, &v2);
        
        // Adding edge v1 --> v2
        adjacencyList[charToIndex(v1)] = AddEdge(adjacencyList[charToIndex(v1)], v2);
        getchar();	// to clear enter input
    }
   
    // Printing Adjacency List
    printf("\nAdjacency List -\n\n");
    for (i = 0; i < SIZE; ++i) {
        printf("adjacencyList[%c] -> ", indexToChar(i));
   
        struct Edge * traverse = adjacencyList[i];
   
        while (traverse != NULL) {
            printf("%c -> ", traverse->vertex);
            traverse = traverse->next;
        }
   
        printf("NULL\n");
    }
   
    return 0;
}

/* Sample Input -

4
A G
A a
T G
a b

*/