#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include <iostream.h>
#include <fstream.h>


struct Graphvertex
{
    int info;
    Graphvertex *next;
};

Graphvertex *list,*list2,*temp,*temp1,*temp2,*new_vertex,*HD;

struct input_array
{
    int source_val;
    int dest_val;

};
struct input_array arcs[15];
int number_vertices;
int number_edges;

void Initialize_list( int number_vertices);
void build_graph (int number_vertices, int number_edges);
void print_graph(int number_vertices);
int add_source(int number_vertices,int m);
void add_sink (int number_edges, int m);
void transpose_graph(int number_vertices);

void main()
{
    ifstream inFile;
    ofstream outFile;
    int x, sum;
    
    inFile.open ("input.txt");
    if (inFile.fail())
    {
        cout << "Could not open input.txt for input\n";
        exit(1);
    }
    outFile.open ("output.txt");
    if (outFile.fail())
    {
        cout << "Could not open output.txt for output\n";
        exit(1);
    }
/* int i;

printf ("please enter the total number of vertices in graph = ");
scanf ("%d", &number_vertices);
printf ("please enter the total number of edges in graph = ");
scanf ("%d", &number_edges);
i=1;
while (i <= number_edges)
{
    printf("please enter the source and destination for the arc %d = ", i);
    scanf ("%d %d", &arcs[i].source_val, &arcs[i].dest_val);
    i++;
    
}
    printf ("the number of vertices in the graph = %d\n", number_vertices);
    printf ("the number of edges in the graph = %d\n", number_edges); */

    list = (Graphvertex *)malloc(sizeof(Graphvertex *) * number_vertices + 1);

    temp = list;

    Initialize_list(number_vertices);

    list=temp;

    build_graph(number_vertices, number_edges);

    printf("The adjancency list of the input graph G=\n\n");

    print_graph(number_vertices);

    transpose_graph(number_vertices);

    list= (Graphvertex *)malloc(sizeof(Graphvertex *) * number_vertices + 1);

    temp =list;

    Initialize_list(number_vertices);

    list=temp;

    build_graph (number_vertices,  number_edges);

    printf("The adjancency list of the transpose graph G(t)=\n\n");

    print_graph(number_vertices);

    outFile << sum;

    inFile.close();
    outFile.close();

}
    
//Initialization//
void Initialize_list(int number_vertices)
{
int j;
for (j=1; j<=number_vertices; j++)
    {
    list->info=j;
    list->next=NULL;
    list++;
    }

}
// build graph//
void build_graph (int number_vertices, int number_edges)
{
    int j,m=1;
    j=1;
    while (list->info<=number_vertices)
    {
        m = add_source (number_edges, m);
        add_sink (number_edges, m);
        list++;
    }
        
}
// add source vertex//
int add_source (int number_edges, int m)
{
    int j;
    j=1;
    while (j<=number_edges)
        {
        if ((list->info == arcs[j].source_val) && (list->next==NULL))
            {
                new_vertex = (Graphvertex *)malloc(sizeof(Graphvertex *) * number_vertices + 1);
                new_vertex->info= arcs[j].dest_val;
                new_vertex->next=NULL;
                list->next = new_vertex;
                m=j+1;
            }
            else
            {
                j++;
            }
        }
    
    return m;
}
// add destination vertex//
void add_sink (int number_edges, int m)
{
    while (m <= number_edges)
            {
                if ((list->info == arcs[m].source_val) && (list->info !=NULL))
                    {
                        HD=list;
                        while (HD->next != NULL)
                        {
                            HD = HD->next;
                        }
                        new_vertex = (Graphvertex *)malloc(sizeof(Graphvertex *) * number_vertices + 1);
                        new_vertex->info = arcs[m].dest_val;
                        new_vertex->next=NULL;
                        HD->next=new_vertex;
                    }
                    m++;
            }
}
// print graph//
void print_graph(int number_vertices)
{
        int flag = 0;
        list=temp;
        while (list->info<=number_vertices)
        {
            if (list->next==NULL)
            {
                printf("%d:",list->info);
            }
            else
            {
                flag = 0;
                HD=list;
                while (HD!=NULL)
                {
                    if (flag == 0)
                        {
                        printf("%d:",HD->info);
                        HD=HD->next;
                        flag=1;
                        }
                    else
                        {
                            printf("%d ",HD->info);
                            HD=HD->next;
                        }
                }
            }
            printf("\n");
            list++;
        }
    }
//Transpose graph//
void transpose_graph (int number_vertices)
{
    int j;
    int x;
    for (j=1; j<=number_edges; j++)
    {
        x = arcs[j].source_val;
        arcs[j].source_val = arcs[j].dest_val;
        arcs[j].dest_val = x;
    }
}

//end of program//