Write a program that checks whether a graph is connected.

Implement the graph using an adjacency list and use DFS.

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node {
	int vertexNumber;
	struct node * next;
} node;
typedef struct {
	int V;
	int E;
	node** Adj;  //array of linked list
} Graph;

Graph* adjacencyList() {
	int i, x, y;
	node * temp, *temp2;
	Graph* G=(Graph*) malloc(sizeof(Graph));

	printf("Enter the number of Vertices: ");
	scanf("%d", &G->V);
	printf("Enter the number of Edges: ");
	scanf("%d", &G->E);
	G->Adj = (node **)malloc(G->V * sizeof(node));
	for (i = 0; i < G->V; i++) {
		G->Adj[i] = (node *)malloc(G->V * sizeof(node));
		G->Adj[i]->vertexNumber = i;
		G->Adj[i]->next = NULL;
	}
 
	for (i = 0; i < G->E; i++) {
		printf("Enter the edge: ");
		scanf("%d %d", &x,&y);
		temp = (node*)malloc(sizeof(node));
		temp->vertexNumber = y;
        temp->next = NULL;
        
		temp2 = G->Adj[x];
		while (temp2->next != NULL)
			temp2 = temp2->next;
		temp2->next = temp;
		
	}
	return G;
}

void DFSTraversal(Graph* G, int index, int Visited[]) 
{
	node * head;
	head =  G->Adj[index];

	//printf("%d ",index);
	
	while(head)
	{
		if(!Visited[head->vertexNumber])
		{
			Visited[head->vertexNumber]=1;
			DFSTraversal(G, head->vertexNumber, Visited);
		}
		head=head->next;
	}
}

void DFS(Graph *G) {
	int i;
	int *Visited;
	Visited = (int *)malloc(G->V * sizeof(int));

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

	// this loop is required if the graph has more than one component
	for (i = 0; i < G ->V; i++)
		if (!Visited[i])
		{
			Visited[i] = 1;
			DFSTraversal(G, i, Visited);
		}
}

int connected(Graph *G)
{
	int i;
	int *Visited;
	Visited = (int *)malloc(G->V * sizeof(int));

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

	Visited[0] = 1;
	DFSTraversal(G, 0, Visited);
	
	for (i = 0; i < G->V; i++)
		if(!Visited[i])
			return  0;
	return 1;
}


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

	if(connected(G))
		printf("Graph connected\n");
	else
		printf("Graph not connected\n");
}

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