1466_min_reorder.cc

#include <stack>
#include <vector>
#include <utility>
 
class Solution {
public:
    int minReorder(int n, std::vector<std::vector<int>>& connections) {
        // Adjancency List for easy traversal
        std::vector<std::vector<std::pair<int, int>>> adjList(n);
        for (const auto& p: connections) {
            adjList[p[0]].push_back({p[1], 1}); // Original direction
            adjList[p[1]].push_back({p[0], 0}); // Against the original direction
        }
 
        int changes = 0;
        std::vector<bool> visited(n, false);
        std::stack<int> stk;
 
        stk.push(0);
        visited[0] = true;
 
        while (!stk.empty()) {
            int currentCity = stk.top(); stk.pop();
 
            for (const auto& p: adjList[currentCity]) {
                if (visited[p.first]) continue;
                // Unvisited neighbouring city
                changes += p.second;
                visited[p.first] = true;
                stk.push(p.first);
            }
        }
 
        return changes;
    }
};