title: graph rerouting algorithm hacker rank
body: <p>I have tried to solve the problem Rerouting at hacker rank. I am posting here for help as competition is over.</p>
  <p><a href="https://www.hackerrank.com/contests/hack-the-interview-v-asia-pacific/challenges/rerouting" rel="nofollow noreferrer">https://www.hackerrank.com/contests/hack-the-interview-v-asia-pacific/challenges/rerouting</a></p>
  <p>I have tried to solve problem using Strong connected components, but test cases failed. I can understand we have to remove cycles. But I stuck how to approach problem. Below is solution i have written. I am looking for guidence how to move forward so that i can apply my knowledge future based on mistakes i made here.  Thanks for your time and help</p>
  <pre><code>int getMinConnectionChange(vector&lt;int&gt; connection) {
      
      // Idea: Get number of strongly connected components.
      int numberOfVertices = connection.size();
      for(int idx = 0; idx &lt; numberOfVertices; idx++) {
          cout &lt;&lt; idx+1 &lt;&lt;&quot;:&quot;&lt;&lt; connection[idx] &lt;&lt; endl;
      }
      stack&lt;int&gt; stkVertices; 
      map&lt;int, bool&gt; mpVertexVisited; //is vertex visited.think this as a chalk mark for nodes visited.
      
      
      int numOFSCCs = 0;
      int currTime = 1;
      for (int vertexId = 0; vertexId &lt; numberOfVertices; vertexId++) {
          // check if node is already visited.
          if (mpVertexVisited.find(vertexId+1) == mpVertexVisited.end()) {
              numOFSCCs++;
              mpVertexVisited.insert(make_pair(vertexId+1, true));
              stkVertices.push(vertexId+1);
              currTime++;
  
              while (!stkVertices.empty()) {
                  int iCurrentVertex = stkVertices.top();
                  stkVertices.pop(); 
                  // get adjacent vertices. In this excercise we have only one neighbour. i.e., edge
                  int neighbourVertexId = connection[iCurrentVertex-1];
                  // if vertex is already visisted, don't insert in to stack.
                  if (mpVertexVisited.find(neighbourVertexId) != mpVertexVisited.end()) {
                      continue;
                  }
                  mpVertexVisited.insert(make_pair(neighbourVertexId, true));
                  stkVertices.push(neighbourVertexId);            
              } // while loop
          } // if condition m_mapVrtxTimes.find(*itr) == m_mapVrtxTimes.end()
      } // for loop of vertices
      return numOFSCCs - 1;
  
  }
  </code></pre>