Reorder Routes to Make All Paths Lead to the City Zero

Intuitionthe destination fixes the direction every road should have

Because the roads form a tree, every city has exactly one path to city 0. Once you imagine city 0 as the root, each road has a required final direction: it must point from a node to its parent, closer to 0. There is no choice between multiple routes, so an edge either already points toward the root or it must be reversed.

The input gives each road in its original direction, but traversal needs to move through the tree in both directions. Store every road twice: once for its original direction and once as a usable undirected connection. Mark the first copy as needing a reversal when you traverse it from the root outward. Then a traversal from 0 counts every edge that points away from 0 exactly once.

Approachturn the directed input into a traversal that remembers orientation

1. 1Build an adjacency list with two entries for every road a -> b: store b with flag 1 under a, and store a with flag 0 under b. This lets the traversal move in either direction while retaining whether the original arrow points along the move.
2. 2Start a BFS at city 0 and mark it visited before putting it in the queue. City 0 is the root, and marking it immediately prevents a later reverse adjacency entry from sending the search back into an already explored branch.
3. 3Remove one city u from the queue and inspect every pair v, direction connected to it. Each unvisited neighbor is the next node on its unique path away from the root, so this is the moment when the edge's original direction can be judged.
4. 4Skip every already visited neighbor. In a tree this avoids following the reverse copy of the edge just crossed; without the check, the artificial undirected representation would repeatedly walk back toward the parent.
5. 5When an unvisited neighbor was stored with flag 1, increment the answer. That flag means the original road is u -> v, away from city 0, so reaching v and then traveling back to the capital requires reversing it.
6. 6Mark v visited and enqueue it after processing the edge. Every city is then expanded once, and every original road is counted once from its parent side rather than being counted again through its reverse adjacency entry.
7. 7Return the count after the queue is empty. At that point every city has been reached and every edge has been classified as either already pointing toward the root or requiring one reversal.

Complexityeach tree edge is classified once

Annotated solutionC++ · iterative BFS · orientation is stored beside every neighbor

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> graph(n);

        for (const vector<int>& connection : connections) {
            int from = connection[0];
            int to = connection[1];

            graph[from].push_back({to, 1});
            graph[to].push_back({from, 0});
        }

        int reversals = 0;
        vector<bool> visited(n, false);
        queue<int> q;

        q.push(0);
        visited[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (const pair<int, int>& edge : graph[u]) {
                int v = edge.first;
                int direction = edge.second;

                if (visited[v]) {
                    continue;
                }

                if (direction == 1) {
                    ++reversals;
                }

                visited[v] = true;
                q.push(v);
            }
        }

        return reversals;
    }
};

The two adjacency entries are the central detail. For an original road from to, the entry under from has flag 1 because walking from the root side to the child follows the original arrow. The reverse entry has flag 0 because walking from the child back to the parent is already the direction needed after rooting the tree. The visited check ensures only the parent-to-child encounter classifies the road.

The DFS alternativesame classification with runtime stack instead of an explicit queue

A recursive DFS uses exactly the same orientation test and has the same asymptotic bounds. It is not an optimisation: the adjacency list and visited array still use O(n), while the traversal stack uses O(n) on a path. It is a reasonable alternative when recursive graph code is natural, but the iterative BFS avoids depending on the runtime call stack for the maximum allowed tree depth.

#include <vector>
#include <utility>

using namespace std;

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> graph(n);

        for (const vector<int>& connection : connections) {
            int from = connection[0];
            int to = connection[1];

            graph[from].push_back({to, 1});
            graph[to].push_back({from, 0});
        }

        vector<bool> visited(n, false);
        return dfs(0, graph, visited);
    }

private:
    int dfs(int u, const vector<vector<pair<int, int>>>& graph,
            vector<bool>& visited) {
        visited[u] = true;
        int reversals = 0;

        for (const pair<int, int>& edge : graph[u]) {
            int v = edge.first;
            int direction = edge.second;

            if (visited[v]) {
                continue;
            }

            reversals += direction;
            reversals += dfs(v, graph, visited);
        }

        return reversals;
    }
};

Common mistakestwo wrong shapes that change what an edge means