title: How to do a DFS on a tree? (not necessarily binary)
body: <p>I have a tree of <code>n</code> nodes (labeled <code>0 to n</code>). I used two vectors to hold the edge information.</p>
  
  <pre><code>typedef std::vector&lt;std::vector&lt;int&gt;&gt; graph;
  </code></pre>
  
  <p>The input is <code>n-1</code> edges in the form:</p>
  
  <pre><code>0 1
  1 2
  2 3
  and so on 
  </code></pre>
  
  <p>I'm told node <code>0</code> is always the root node.
  I scan the edges using the following:</p>
  
  <pre><code>for (int i = 0; i &lt; n-1; i++) {
      scanf("%d %d", &amp;a, &amp;b);
      g[a].push_back(b);
      g[b].push_back(a); // the second approach doesn't use this line
  }
  </code></pre>
  
  <p>This is my simple dfs:</p>
  
  <pre><code>void dfs(graph &amp;g, int v) {
      std::vector&lt;int&gt; visited; // I don't use a visited array for the second approach
      for (int i = 0; i &lt; g.size(); i++) {
          visited.push_back(0);
      }
      std::stack&lt;int&gt; s;
      std::set&lt;int&gt; t;
      s.push(v);
      while (!s.empty()) {
          int i = s.top(); s.pop();
          // do stuff
          for (int i = 0; i &lt; g[v].size(); i++) {
              if (!visited[i]) {
                  visited[i] = true;
                  s.push(g[v][i]);
              }
          }
      }
  }
  </code></pre>
  
  <p>For example say we have 4 nodes and the following edges:</p>
  
  <pre><code>0 1
  0 2
  3 2
  2 4
  </code></pre>
  
  <p>Say that I'm interested in the sub tree starting at <code>2</code>. The above approach won't work because I'm inserting undirected edges <code>0 2</code> and <code>2 0</code>. So when I start my <code>dfs</code> at <code>2</code> I add node <code>0</code> to my stack which is wrong.</p>
  
  <p>I tried another approach of only inserting the edges given only but that also didn't work because in the example I would've inserted <code>3 2</code> which is an edge from <code>3</code> to node <code>2</code> and so when I start my <code>dfs</code> at node <code>2</code> I won't be able to reach node <code>3</code>.</p>
  
  <p>I feel like the problem is simple and I'm missing some big idea! </p>