title: Running Time of Connected Component Count Algorithm
body: <p>I've been looking into connected components, and came across this description on <a href="https://en.wikipedia.org/wiki/Connected_component_(graph_theory)" rel="nofollow noreferrer">Wikipedia</a>:</p>
  
  <blockquote>
    <p>It is straightforward to compute the connected components of a graph
    in linear time (in terms of the numbers of the vertices and edges of
    the graph) using either breadth-first search or depth-first search. In
    either case, a search that begins at some particular vertex v will
    find the entire connected component containing v (and no more) before
    returning. To find all the connected components of a graph, loop
    through its vertices, starting a new breadth first or depth first
    search whenever the loop reaches a vertex that has not already been
    included in a previously found connected component.</p>
  </blockquote>
  
  <p>What would be the run time of this operation? I've come across sources that say connected components are done in <code>O(n)</code> time. However, from what I can tell, in the worst case where each vertex is its own connected component, this algorithm will have to perform n DFS/BFS operations, each of which is itself <code>O(n)</code> time. Therefore, shouldn't the run time of this be <code>O(n^2)</code>?</p>