title: Graphs and depth-first search using vectors in C++
body: <p>I saw the following code for making a graph and doing depth-first search on it. Can you explain me the use of vector g here. In the second function, how it is written as a 2-dimensional thing. Please explain the whole process clearly, on using vectors for this purpose. Problem is following:--- A Company is connected to n cities numbered from 1 to n. Currently the Headquarter of company is situated at index hq1. Each pair of connected cities are connected both ways. The connection is such that there is exactly one connection from the Headquarter to each city. The map of the connected cities is kept in the following way: for each city i, different from the Headquarter, there is kept number ci — index of the last city on the way from the Headquarter to i.</p>
  
  <p>The company decided to move the Headquarter from city hq1 to city hq2. So, after this change the old representation of the map as described above became incorrect. Please, help the company to find out a new map in the way described above.</p>
  
  <p>Input</p>
  
  <p>The first line contains the number of test cases(0 &lt; T &lt;= 10 ). The next line contains three space-separated integers n, hq1, hq2 (2 ≤ n ≤ 2*10^4, 1 ≤ hq1 ≠ hq2 ≤ n) — number of connected cities, index of the old Headquarter and index of the new Headquarter, respectively.</p>
  
  <p>The following line contains n - 1 space-separated integers — the old representation of the map. For each city, other than hq1, there is given integer ci — index of the last city on the way from the Headquarter to city i. All the cities are described in order of increasing indexes.</p>
  
  <p>Output</p>
  
  <p>Output n - 1 numbers — new representation of the map in the same format. The solution is given below. </p>
  
  <pre><code>vector &lt; int &gt;g[10005];
  void make_graph()
  {
      int k = 1;
      for (int i = 1; i &lt;= n; i++)
      {
          if (i == h1)
              continue;
          int x;
          cin &gt;&gt; x;
          g[x].push_back (i);
          g[i].push_back (x);
      }
  
  }
  
  int visited[20004], parent[20004];
  
  void dfs(int x)
  {
      visited[x] = 1;
      for (int i = 0; i &lt; g[x].size (); i++)
      {
          int j = g[x][i];
          if (j == parent[x])
              continue;
          parent[j] = x;
          dfs (j);
      }
  
      return;
  }
  
  
  
  int
  main ()
  {
   int t;
   cin &gt;&gt; t;
   while (t--)
     {
        cin &gt;&gt; n &gt;&gt; h1 &gt;&gt; h2;
        make_graph ();
        dfs (h2);
        for (int i = 1; i &lt; n; i++)
          {
        if (i == h2)
         continue;
        cout &lt;&lt; parent[i] &lt;&lt; " ";
      }
    if (n != h2)
  cout &lt;&lt; parent[n] &lt;&lt; endl;
    else
  cout &lt;&lt; endl;
    memset (parent, 0, sizeof (parent));
    memset (visited, 0, sizeof (parent));
    for (int i = 1; i &lt;= n; i++)
  g[i].clear ();
  
     }
  
    return 0;
    }
  </code></pre>