#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main()

{

// The MAX_LENGTH should be defined according to the maximum length of the lines in the input file:

#define MAX_LENGTH 200

// Load the Adjacency list file:

FILE * Input_file;

Input_file=fopen("in7.txt","r"); // PLease change the input file name here

// Initiallization:

char Row_str[MAX_LENGTH]; // Each row of the input file

char *pch;

int Num_vert=0; //Number of vertices

int i=0, j=0, k=0;

int Head_node[MAX_LENGTH][MAX_LENGTH]; // Head_node[i][j]= The head node of the j-th edge of node i

int Edge_Charge[MAX_LENGTH][MAX_LENGTH];

for (i=0;i<MAX_LENGTH;i++){

for (j=0;j<MAX_LENGTH;j++){

Head_node[i][j]=0;

Edge_Charge[i][j]=0;

}

}

int Node_Charge[MAX_LENGTH];

int indegree[MAX_LENGTH];

for (k=0;k<MAX_LENGTH;k++){

indegree[k]=0;

Node_Charge[k]=0;}

int Num_edges=0;

int Vertex;

int Topological_Order[MAX_LENGTH];

i=0;j=0;

// Load the input file to an array

//printf("The Adjacency list is:\n\n");

while(fgets(Row_str, MAX_LENGTH, Input_file)!=NULL){

puts(Row_str);

Node_Charge[Num_vert]++;

Num_vert++;

pch=strtok(Row_str," ");

while (pch!=NULL){

Vertex=atoi(pch);

if (Vertex!=0){

// Find head of each edge(=the node that the edge enters it) and initiallizing in-degree array

if (j!=0){

Head_node[i][j-1]=Vertex;

Num_edges++;

indegree[Vertex-1]++;

Edge_Charge[i][Vertex-1]+=2; // 1 charge per reading edge, 1 charge for counting in-degree

}

}

pch = strtok( NULL, " " );

j++;}

i++;j=0;}

printf("\n_______________________________________________\n");

printf("\n\nTotal number of Vertices = %d and Edges=%d\n",Num_vert,Num_edges);

printf("\n_______________________________________________\n");

//TOPOLOGICAL SORTING:

int order=0;

int check_cycle=1;

i=0;k=1;

while (i<Num_vert){

if (indegree[i]==0){

Node_Charge[i]+=2; // 2 charges for pop and push from in-degree to topological order

Topological_Order[order]=i+1;

order++;

indegree[i]=-1;

k++;

for(j=0;j<Num_vert;j++){

if ((Head_node[i][j])>0){

indegree[(Head_node[i][j])-1]--;

Edge_Charge[i][(Head_node[i][j])-1]++;} // modify in-degree by deleting related edges, and charging them

}

i=0;

check_cycle=0;

}

else

i++;check_cycle=1;

}

if (check_cycle==1 && k<Num_vert){

printf("This graph has a cycle!\n");

return 1;

}

printf("\n");

printf("\nTopological Order:\n");

for (i=0;i<Num_vert;i++)

fprintf(stdout,"%d ",Topological_Order[i]);

printf("\n_______________________________________________\n");

printf("\n");

int Total_Node_Charge=0;

for (i=0;i<Num_vert;i++){

fprintf(stdout,"Vertex %d Charge = %d\n",i+1,Node_Charge[i]);

Total_Node_Charge+=Node_Charge[i];

}

printf("\nTotal number of operations charged to all vertices is :%d\n",Total_Node_Charge);

printf("\n_______________________________________________\n");

int Total_Edge_Charge=0;

for (i=0;i<Num_vert;i++){

for(j=0;j<Num_vert;j++){

if (Edge_Charge[i][j] != 0)

fprintf(stdout,"The Charge of Edge from Vertex %d to Vertex %d = %d\n",i+1,j+1,Edge_Charge[i][j]);

Total_Edge_Charge+=Edge_Charge[i][j];}}

printf("\nTotal number of operations charged to edges is : %d\n",Total_Edge_Charge);

printf("\n_______________________________________________\n");

int Total_operations=Total_Edge_Charge+Total_Node_Charge;

printf("\nTotal number of operations is : %d\n",Total_operations);

printf("\n_______________________________________________\n");

fclose(Input_file);

return 0;

}