title: Counting number of trees in a forest
body: <p>I was trying to answer the following question from a textbook.</p>
  
  <blockquote>
    <p>Given n nodes of a forest and their edges, describe and prove an algorithm that finds the number of trees in the forest.</p>
  </blockquote>
  
  <p>Take for instance this graph:</p>
  
  <p><img src="https://i.stack.imgur.com/eHCWC.png" alt="graph"></p>
  
  <p>Suppose that we explore it with a DFS, starting at vertex 0, that visits the vertices in the following order: 0, 2, 1, 5, 4, 3, 6. </p>
  
  <p>The corresponding DFS forest will look like this:</p>
  
  <p><img src="https://i.stack.imgur.com/1jK8Z.png" alt="this">.</p>
  
  <p>The above forest contains two trees and I think we can use the below algorithm to count the number of trees in a forest. [<a href="https://www.geeksforgeeks.org/count-number-trees-forest/" rel="nofollow noreferrer">Source of algorithm</a>]</p>
  
  <ol>
  <li>Apply DFS on every node.</li>
  <li>Increment count by one if every connected node is visited from one source.</li>
  <li>Again perform DFS traversal if some nodes yet not visited.</li>
  <li>Count will give the number of trees in forest.</li>
  </ol>
  
  <p>My question is: How can I prove that this algorithm is correct, and is there a more efficient algorithm to get the number of trees in a forest?</p>