title: Using BFS or DFS to determine the connectivity in a non connected graph?
body: <p>How can i design an algorithm using <strong>BFS or DFS</strong> algorithms in order to <strong>determine the connected components of a non connected graph</strong>, the algorithm must be able to <strong>denote the set of vertices of each connected component</strong>.</p>
  
  <p><strong>This is my aproach:</strong></p>
  
  <blockquote>
    <p>1) Initialize all vertices as not visited.</p>
    
    <p>2) Do a DFS traversal of graph starting from any arbitrary vertex v.
    If DFS traversal doesn’t visit all vertices, then return false.</p>
    
    <p>3) Reverse all arcs (or find transpose or reverse of graph)</p>
    
    <p>4) Mark all vertices as not-visited in reversed graph.</p>
    
    <p>5) Do a DFS traversal of reversed graph starting from same vertex v
    (Same as step 2). If DFS traversal doesn’t visit all vertices, then
    return false. Otherwise return true.</p>
    
    <p>The idea is, if every node can be reached from a vertex v, and every
    node can reach v, then the graph is strongly connected. In step 2, we
    check if all vertices are reachable from v. In step 4, we check if all
    vertices can reach v (In reversed graph, if all vertices are reachable
    from v, then all vertices can reach v in original graph).</p>
  </blockquote>
  
  <p>Any idea of how to improve this solution?. </p>