One of the applications of DFS is to find the number of connected components in a graph.In graph theory, a connected component of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph.

**Algorithm-**

A depth first search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning.To find all the connected components of a graph, loop through its vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

Another application is to find if the given graph is a tree or not.A tree is an undirected graph which is connected and does not have cycles.

**Properties of a tree-**

1.The tree should have only one connected component ie. it is not a disconnected graph.

2.If the graph has N vertices and N-1 edges,then it is a tree.This condition ensures that no cycles are formed.

**Algorithm-**

For a graph to be a tree,both the above conditions must be satisfied.Number of components is found using the above algorithm and it should be 1.Then,the second relation must be verified.

**Code-**

#include<stdio.h> #include<vector> using namespace std; vector<int>arr[10005]; int n,a,b,j=0,m; int color[100005]; //counter counts the number of components int counter; void dfs(int node) { color[node]=2;//marking the visited nodes for(int i=0;i<arr[node].size();++i) { if(color[arr[node][i]]==0) { dfs(arr[node][i]); } } } int main() { int t,p; int i; counter=0; p=1; j=0; // n is the number of vertices // m is the number of edges scanf("%d %d",&n,&m); //clearing the arrays and vectors for(i=0;i<n;i++) arr[i].clear(); for(i=0;i<n;++i){ color[i]=0; } while(j<m){ //a and b denote the starting and ending points of the edge scanf("%d %d",&a,&b); //maintaining the adjacency lists arr[a-1].push_back(b-1); arr[b-1].push_back(a-1); j++; } //looping through the vertices for(i=0;i<n;++i) { if(color[i]==0) { dfs(i); counter++; } } printf("Number of components is %d\n",counter); if((m==n-1)&&(counter==1))printf("IT IS A TREE\n"); else printf("NOT A TREE\n"); return 0; }