In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. 

Write a program that finds the number of connected compoenents in an undirected graph.

Difficulty level
This exercise is mostly suitable for students 
#include<stdio.h>
#include<stdlib.h>
#define N 20

typedef struct {
	int V;
	int E;
	int **Adj; // since we need 2 dimensional matrix
} Graph;


Graph* adjacencyMatrix() {
	int i, u, v;
	Graph* G=(Graph*) malloc(sizeof(Graph));
	scanf("%d", &G->V);
	scanf("%d", &G->E);
	G->Adj = (int **)malloc(G->V * sizeof(int*));
	for (u = 0; u < G->V; u++)
		G->Adj[u] = (int *)malloc(G->V * sizeof(int));

	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 the edge: ");
		scanf("%d %d", &u,&v);
		// for undirected graph, set both
		G->Adj[u][v] = 1;
		G->Adj[v][u] = 1;
	}
	return G;
}

void DFSTraversal(Graph* G, int index, int Visited[]) {
	int v;
 	//printf("%d ",index);
	for (v = 0; v < G->V; v++) {
		if (!Visited[v] && G->Adj[index][v])
		{
		    Visited[v]=1;
			DFSTraversal(G, v, Visited);
		 }
	}
}


void DFSCC(Graph *G) {
	int i, numCC;
	int *Visited;

	numCC=0;

	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])
		    ++numCC,DFSTraversal(G, i, Visited);
		   //	printf("CC %d: ", ++numCC), DFSTraversal(G, i, Visited), printf("\n");	
    	printf("%d\n", numCC);
}


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

int main()
{
    int tests;
    scanf("%d",&tests);
    while(tests--)
    {
	    test();
    }
	return 0;
}


/*

9 7
0 1
1 2
1 3
2 3
3 4
6 7
6 8

3


        
*/
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Finding a value in an array using jump search