#include<iostream>
#define NODES 6
#include<stdlib.h>

using namespace std;

// Nodes of the adjacency lists
typedef struct node
{
    int name;
    int weight;
    struct node* next;
}node;


//Header of the adjacency lists
typedef struct graph_node
{
    int name;
    int visited;
    int parent;
    struct node* list;
}graph_node;

void add_edge(int i,int w,int j,graph_node g[])
{
    node* temp = g[i].list;

    node* new_node = (node*) malloc(sizeof(node));
    new_node->name = j;
    new_node->weight = w;
    new_node->next=NULL;
    if( temp==NULL)
    {
        g[i].list = new_node;
        return;
    }
    else
    {
        g[i].list = new_node;
        new_node->next = temp;
        return;
    }
}

// Used for noting the paths
int vertex_list[100];
int vertex_count = 0;


void printList()
{
    for(int i=0;i<vertex_count;i++)
    {
        cout<<vertex_list[i]<<" -- ";
    }
    cout<<"\n";
}

void findPaths(graph_node g[],int start)
{
    vertex_list[vertex_count++] = start;
    g[start].visited = 1;
    node* temp = g[start].list;
    int flag = 0;
    // Flag is used to check the dead end of the path
    while(temp)
    {
        if(g[temp->name].visited == 0)
        {
            flag = 1;
            findPaths(g,temp->name);
        }
        temp = temp->next;
    }
    if(flag == 0)
    {
        // If all are having visited == 1 , there is no new node, so its a dead end
        printList();
    }
    g[start].visited = 0;
    vertex_count--;
}

void initGraph(graph_node g[])
{
    add_edge(0,4,1,g);
    add_edge(1,1,2,g);
    add_edge(1,4,3,g);
    add_edge(2,2,4,g);
    add_edge(0,2,5,g);
    add_edge(5,2,3,g);
}

void printGraph(graph_node g[])
{
    for(int i=0;i<NODES;i++)
    {
        cout<<"\t\t"<<g[i].name<<" ----> ";
        node* temp = g[i].list;
        while(temp)
        {
            cout<<temp->name<<" "<<" ";
            temp = temp->next;
        }
        cout<<"\n";
    }
}


int main()
{
    graph_node graph[NODES];

    for(int i=0;i<NODES;i++)
    {
        graph[i].name = i;
        graph[i].list = NULL;
        graph[i].visited = 0;
    }
    cout<<"THis is the graph adjacency list : \n";
    initGraph(graph);
    printGraph(graph);
    cout<<"These are the following paths : \n";
    findPaths(graph,0);
}