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}}Expected Output
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;
void add_edge(vector<int> adj_matrix[], int u, int v)
{
adj_matrix[u].push_back(v);
adj_matrix[v].push_back(u);
}
void dfs(int u, vector<int> adj_matrix[],
vector<bool> &visited)
{
visited[u] = true;
for (int i=0; i<adj_matrix[u].size(); i++)
if (visited[adj_matrix[u][i]] == false)
dfs(adj_matrix[u][i], adj_matrix, visited);
}
int countTrees(vector<int> adj_matrix[], int V)
{
vector<bool> visited(V, false);
int res = 0;
for (int u=0; u<V; u++)
{
if (visited[u] == false)
{
dfs(u, adj_matrix, visited);
res++;
}
}
return res;
}
int main()
{
int V = 5;
vector<int> adj_matrix[V];
add_edge(adj_matrix, 0, 1);
add_edge(adj_matrix, 0, 2);
add_edge(adj_matrix, 3, 4);
cout << countTrees(adj_matrix, V);
}
import java.io.*;
import java.util.*;
class Graph
{
private int V;
private LinkedList<Integer> adj_matrix[];
Graph(int v)
{
V = v;
adj_matrix = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj_matrix[i] = new LinkedList();
}
void add_edge(int v, int w)
{
adj_matrix[v].add(w);
}
void dfs(int v,boolean visited[])
{
visited[v] = true;
Iterator<Integer> i = adj_matrix[v].listIterator();
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);
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(3, 4);
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))
