Count Trees in a Forest

Count Trees in a Forest is a clean introduction to connected components. A forest is just a graph with no cycles, and each separate piece of it is one tree. Counting the trees means counting the connected pieces — a single graph traversal does it.

The slow way first

You might try comparing every vertex against every other to see which ones are connected, then grouping them. Figuring out reachability for each pair separately is wasteful — you end up re-walking the same edges over and over, and the bookkeeping balloons toward O(n²) or worse.

The question to ask: can I discover a whole connected piece in one shot, then never touch it again? Yes — a single DFS (or BFS) from any vertex floods its entire component. So each component costs work proportional to its own size, and the total is linear.

The idea: one DFS per tree

Keep a seen set. Sweep the vertices 0..n-1 in order. When you reach a vertex that is not in seen, you have found a brand-new tree no earlier DFS reached — so add 1 to the count and run a DFS that marks every vertex reachable from it. When the sweep later lands on those already-marked vertices, you skip them. The number of times you launch a DFS is exactly the number of trees.

The key insight: a vertex only triggers a count increment if no prior DFS had already reached it. That guarantees we count each component exactly once.

Walk through it

Step through the animation. Everything starts dimmed (unvisited). The sweep hits vertex 0 first — unvisited, so trees becomes 1 and DFS floods 0 → 1 → 2, painting them one color. The sweep skips 1 and 2 because they are already marked. Vertex 3 is unvisited, so trees becomes 2 and DFS claims 3 → 4. Finally vertex 5, which has no edges, is its own tree — trees becomes 3. Three colors, three trees.

Pseudocode

build an adjacency list from the edges (undirected: add both directions)
make an empty set "seen"
 
define dfs(v):
    add v to seen
    for each neighbor nb of v:
        if nb not in seen:
            dfs(nb)
 
trees = 0
for v in 0 .. n-1:
    if v not in seen:
        trees += 1            # a new connected component
        dfs(v)                # claim the whole piece
return trees

The Python solution

def count_trees(n, edges):
    graph = {v: [] for v in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    seen = set()
 
    def dfs(v):
        seen.add(v)
        for nb in graph[v]:
            if nb not in seen:
                dfs(nb)
 
    trees = 0
    for v in range(n):
        if v not in seen:
            trees += 1
            dfs(v)
    return trees

• We build an adjacency list; because the graph is undirected, each edge is added in both directions.
• seen is the set of vertices already claimed by some DFS.
• dfs(v) marks v, then recurses into every unvisited neighbor — flooding the whole component.
• The sweep for v in range(n) is the heart: an unvisited vertex means a new tree, so we bump trees and launch a DFS.
• Vertices reached inside a DFS land in seen, so the sweep harmlessly skips them later.

Complexity

The whole algorithm is O(V + E): the sweep visits each vertex once, and across all DFS launches each vertex and edge is processed exactly once. The space is the adjacency list plus the seen set plus the recursion stack.

When this pattern shows up

Practice