# Count number of trees in a forest

### Problem Statement

Given a forest with edge representation, find the number of trees in the forest.

### Example Input

`edges = {{0, 1}, {0, 2}, {3, 4}, {4, 5}, {5, 6}}`

2

### Approach

The idea is to apply Depth First Search on every node. If every connected node is visited from one source then increment count by one. If some nodes yet not visited again perform DFS traversal. Return the count.

### Implementation

```#include<bits/stdc++.h>
using namespace std;

{
}

vector<bool> &visited)
{
visited[u] = true;
}

{
vector<bool> visited(V, false);
int res = 0;
for (int u=0; u<V; u++)
{
if (visited[u] == false)
{
res++;
}
}
return res;
}

int main()
{
int V = 5;

}```

```import java.io.*;
import java.util.*;

class Graph
{
private int V;

Graph(int v)
{
V = v;
for (int i = 0; i <  v; ++i)
}

{
}

void dfs(int v,boolean visited[])
{

visited[v] = true;
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
dfs(n,visited);
}
}
}

int countTrees()
{

boolean visited[] = new boolean[V];
int res = 0;

for (int i = 0; i < V; ++i)
{
if (visited[i] == false)
{
dfs(i, visited);
res ++;
}
}
return res;
}

public static void main(String args[])
{
Graph g = new Graph(5);

System.out.println(g.countTrees());
}
}
```

```# Program to count number
# of trees in a forest.

def Insert_Edge(Graph, u, v):
Graph[u].append(v)
Graph[v].append(u)

def Depth_First_Search_Traversal(u, Graph, Check_visited):
Check_visited[u] = True
for i in range(len(Graph[u])):
if (Check_visited[Graph[u][i]] == False):
Depth_First_Search_Traversal(Graph[u][i], Graph, Check_visited)

def Count_Tree(Graph, V):
Check_visited = [False] * V
res = 0
for u in range(V):
if (Check_visited[u] == False):
Depth_First_Search_Traversal(u, Graph, Check_visited)
res += 1
return res

# Driver code
if __name__ == '__main__':

V = 7
Graph = [[] for i in range(V)]
Insert_Edge(Graph, 0, 1)
Insert_Edge(Graph, 0, 2)
Insert_Edge(Graph, 3, 4)
Insert_Edge(Graph, 4, 5)
Insert_Edge(Graph, 5, 6)
print(Count_Tree(Graph, V))```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]