Consider the following linked list representation of a directed weighted graph

typedef struct node {
    int vertexNumber;
    int weight;
    struct node * next; // circular linked list
} node;

 

typedef struct {
     int V;
     int E;
     node** Adj; // array of circular linked lists
} Graph;

 

A vertex is said to be $\texttt{valid}$ if the sum of the weights of the indegree edges is equal to that of the outdegree edges.

  1. Write a function that returns the number of valid vertices in a directed weighted graph passed as parameters.
  2. Without performing any calculations, give the worst case time complexity of your function. Justify your answer.
Difficulty level
This exercise is mostly suitable for students 
int nb_val(Graph *G) {
	int u, v, i;
	node * temp;
	int *in, *out;
	int count;

	in = (int *)malloc(G->V * sizeof(int));
	out = (int *)malloc(G->V * sizeof(int));

	for (i = 0; i < G->V; i++)
		in[i] = out[i] = 0;


	for (u = 0; u < G->V; u++)
	{
		temp = G->Adj[u];
		count = 0;
		G->Adj[u] = G->Adj[u]->next;
		while (temp != G->Adj[u])
		{
			count+=G->Adj[u]->weight;
			in[G->Adj[u]->vertexNumber]+=G->Adj[u]->weight;
			G->Adj[u] = G->Adj[u]->next;
		} 
		out[u]=count;
	}


	count =0;
	for (u = 0; u < G->V; u++)
	{
		printf("u=%d in=%d out=%d\n",u,in[u],out[u]);
		if(in[u]==out[u])
			count ++;
	}
	return count;
}
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Min-max heaps