Zahraa has just finished college and decided to go out with friends. Zahraa has some strange habits and thus she decided to celebrate this important moment of her life drinking sugar a lot. She will start drinking beverages with low sugar content, like water, and then will move to a beverage that contains more sugar, like Pepsi, until there are no more available beverages. Once Zahraa starts to drink Pepsi she will not drink water again, so the sugar content of the beverages never decreases with the time.
You should help Zahraa by indicating an order in which she can drink the beverages in the way she wishes.

The input is as follows:

• A number \( N \), \( 1 \leq N \leq 100\), indicating the number of available beverages.
• Followed with \( N \) lines, containing the name of each beverage, a name has less than 51 characters and has no white spaces.
• A number \( M \), \(1 \leq M \leq 200\), in the form \(B_1\) \(B_2\), indicating that beverage \(B_2\) has more sugar that beverage \(B_1\), so Zahraa should drink beverage \(B_1\) before she starts drinking beverage \(B_2\). Be sure that this relation is transitive, so if there is also a relation \(B_2\) \(B_3\) Zahraa should drink \(B_1\) before she can drink \(B_3\).
  
  

As output, print the message: "\(\texttt{Zahraa should drink beverages in this order:}\)  \(B_1 B_2 \cdots B_N.\)", where \( B_1 B_2 \cdots B_N\) is a list of the beverages such that the sugar content of beverage \(B_i\) is not less than the sugar content of beverage \( B_{i-1} \).

****************************************************
****************************************************

		USING ADJACENCY MATRIX

****************************************************
****************************************************

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 20

typedef int element;

typedef struct 
{
	element data[N]; /* queue content */
	int front, length;
} queue;

 


queue CreateQueue()
{
	queue q;
	q.front = 0; q.length=0;
	return q;
}
int isEmptyQueue(queue q)
{
	return q.length == 0;
}

int isFullQueue(queue q)
{
	return q.length ==N;
}

int EnQueue(queue *q, element e)
{
	if (isFullQueue(*q)) return 0;
	q->data[(q->front + q->length)%N] = e;
	q->length = q->length + 1;
	return 1;
}

int DeQueue(queue *q)
{
	if (isEmptyQueue(*q)) return 0;
	q->front=(q->front + 1) % N;
	q->length--;
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.data[q.front];
	return 1;
}

typedef struct {
	int V;
	int E;
	int **Adj;  
	char **beverages;
} Graph;


Graph* adjacencyMatrix() {
	int i, u, v, istr1,istr2;
	char str1[50], str2[50];
	Graph* G=(Graph*) malloc(sizeof(Graph));

	printf("Enter the number of Beverages: ");
	scanf("%d", &G->V);
	G->beverages = (char **)malloc(G->V * sizeof(char*));
	G->Adj = (int **)malloc(G->V * sizeof(int*));
	for (u = 0; u < G->V; u++) {
		printf("Enter beverage number %d: ", u+1);
		scanf("%s",str1);
		G->beverages[u]= (char *)malloc(strlen(str1) * sizeof(char));
		strcpy(G->beverages[u], str1);
		G->Adj[u] = (int *)malloc(G->V * sizeof(int));
	}

	printf("Enter the number of relations between beverages: ");
	scanf("%d", &G->E);
	

	for (u = 0; u<G->V; u++)
		for (v = 0; v<G->V; v++)
			G->Adj[u][v] = 0;
	for (i = 0; i < G->E; i++) {
		printf("Enter 2 beverages: ");
		scanf("%s %s", str1,str2);
		// search for str1 index in the beverages tables
		for (u = 0; u<G->V; u++){
			if (strcmp(str1, G->beverages[u]) == 0)
				istr1 = u;
			else
				if (strcmp(str2, G->beverages[u]) == 0)
					istr2 = u;
		}

		G->Adj[istr1][istr2] = 1;
	}
	return G;
}


void topologicalSort(Graph *G) {
	queue q;
	int v, w;
	int *indegree;

	indegree= (int *)malloc(G->V * sizeof(int));
	for (v = 0; v < G->V; v++)
		indegree[v] = 0;

	for (v = 0; v < G->V; v++)
		for (w = 0; w < G->V; w++)
			if (G->Adj[v][w] == 1)
				indegree[w]++;
 
       
	q = CreateQueue();
	printf("Zahraa should drink beverages in this order:");

	 
	for (v = 0; v < G->V; v++)
		if (indegree[v]==0)
			EnQueue(&q, v);
	while (Front(q,&v)) {
		DeQueue(&q);
		for (w = 0; w < G->V; w++)
			if (G->Adj[v][w] == 1)
				if(--indegree[w] == 0)
					EnQueue(&q, w);
		printf(" %s", G->beverages[v]);

	}
 
	puts(".\n");
}
 

void test() {
	Graph *G = adjacencyMatrix();
	topologicalSort(G);
}


int main()
{
	test();
	return 0;
}




****************************************************
****************************************************

		USING ADJACENCY LIST

****************************************************
****************************************************


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 20

typedef int element;

typedef struct 
{
	element data[N]; /* queue content */
	int front, length;
} queue;


typedef struct node {
	int vertexNumber;
	struct node * next;
} node;
typedef struct {
	int V;
	int E;
	node** Adj;  
	char **beverages; 
} Graph;




queue CreateQueue()
{
	queue q;
	q.front = 0; q.length=0;
	return q;
}
int isEmptyQueue(queue q)
{
	return q.length == 0;
}

int isFullQueue(queue q)
{
	return q.length ==N;
}

int EnQueue(queue *q, element e)
{
	if (isFullQueue(*q)) return 0;
	q->data[(q->front + q->length)%N] = e;
	q->length = q->length + 1;
	return 1;
}

int DeQueue(queue *q)
{
	if (isEmptyQueue(*q)) return 0;
	q->front=(q->front + 1) % N;
	q->length--;
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.data[q.front];
	return 1;
}

 




Graph* adjacencyList() {
	int i, x, y, u,  istr1,istr2;
	node * temp, *temp2;
	char str1[50], str2[50];
	Graph* G=(Graph*) malloc(sizeof(Graph));


	printf("Enter the number of Beverages: ");
	scanf("%d", &G->V);
	G->beverages = (char **)malloc(G->V * sizeof(char*));
	G->Adj = (node **)malloc(G->V * sizeof(node));
	for (u = 0; u < G->V; u++) {
		printf("Enter beverage number %d: ", u+1);
		scanf("%s",str1);
		G->beverages[u]= (char *)malloc(strlen(str1) * sizeof(char));
		strcpy(G->beverages[u], str1);

		G->Adj[i] = (node *)malloc(G->V * sizeof(node));
		G->Adj[i]->vertexNumber = i;
		G->Adj[i]->next = NULL;
	}


	printf("Enter the number of relations between beverages: ");
	scanf("%d", &G->E);

	for (i = 0; i < G->E; i++) {
		printf("Enter 2 beverages: ");
		scanf("%s %s", str1,str2);
		// search for str1 index in the beverages tables
		for (u = 0; u<G->V; u++){
			if (strcmp(str1, G->beverages[u]) == 0)
				istr1 = u;
			else
				if (strcmp(str2, G->beverages[u]) == 0)
					istr2 = u;
		}

		temp = (node*)malloc(sizeof(node));
		temp->vertexNumber = istr2;
        	temp->next = NULL;
        
		temp2 = G->Adj[istr1];
		while (temp2->next != NULL)
			temp2 = temp2->next;
		temp2->next = temp;
		
	}
	return G;
}

 

void topologicalSort(Graph *G) {
	queue q;
	int v, w;
	int *indegree;
	node * head;


	indegree= (int *)malloc(G->V  * sizeof(int));
	for (v = 0; v < G->V; v++)
		indegree[v] = 0;

 
	for (v = 0; v < G->V; v++)
	{
		head=G->Adj[v]->next;
		while(head)
		{
			indegree[head->vertexNumber]++;
			head=head->next;
		}
	}
       
	q = CreateQueue();
 
 	printf("Zahraa should drink beverages in this order:");

 
	for (v = 0; v < G->V; v++)
		if (indegree[v]==0)
			EnQueue(&q, v);

	while (Front(q,&v)) {
		DeQueue(&q);
		head=G->Adj[v]->next;
		while(head)
		{
			if(--indegree[head->vertexNumber] == 0)
				EnQueue(&q, head->vertexNumber);
			head=head->next;
		}
		printf(" %s", G->beverages[v]);

	}
	puts(".\n");
}



void test() {
	Graph *G = adjacencyList();
	topologicalSort(G);
}

int main()
{
	test();
	return 0;
}