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}}

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))

 

Scroll to Top