1466. Reordered Routes

Reorder Routes to Make All Paths Lead to the City Zero

Quite an interesting problem. It asks us in a directed graph:

what's the minimum number of directed edges to flip so that every city can reach city 0?

Given to us are $n$ cities and only $n - 1$ edges, so there will be no cycles.

What Does a Graph Look Like If Every City Can Reach City 0?

It must be that when we start searching from city 0,

all edges connected to city 0 point into city 0.

City 0 has no outgoing edges at all. Then:

I. Suppose an incoming edge of city 0 comes from city $i$.

Then the only outgoing edge of city $i$ must lead to city $0$.

As mentioned earlier, this graph contains $n$ nodes and $n - 1$ edges.

Thus, city 0 has no outgoing edges, while every other city has exactly one outgoing edge.

II. Suppose an incoming edge of city $i$ comes from city $j$.

Then the only outgoing edge of city $j$ must lead to...yes: city $i$.

The reason is the exact same as in Part I.

III. Suppose an incoming edge of city $j$ comes from city $k$, so...

Recursive Relationship of I, II, and III

I believe you have already noticed that I, II, and III are recursive.

But this recursive relationship doesn't have to require DFS in this problem.

BFS can also handle this recursive relationship easily.

Keep reading and you'll see why. 😁

Temporarily Ignore Original Edges' Directions

We prepare a FIFO queue.

Initially, queue contains only city 0, meaning that we start from city 0.

As long as queue isn't empty, we:

remove city $i$ from queue's front and mark it as visited.

Then examine every edge connected to city $i$.

As long as city $j$, on the other end of this under-examination edge,

hasn't been visited, we push city $j$ into queue.

At the same time, we check direction of the edge between city $i$ and $j$.

If this edge points from city $i$ to $j$,

it means this edge must be reversed, so we raise reversal count by one.

C++

#include <queue>
#include <vector>
using namespace std;

int find_min_reorders(int n, vector<vector<int>>& connections) {
    vector<vector<int>> srcNodes(n, vector<int>()), tgtNodes(n, vector<int>());
    vector<bool> visited(n, false);

    for (const auto& edge : connections) {
        int srcNode = edge[0], tgtNode = edge[1];

        srcNodes[tgtNode].push_back(srcNode);
        tgtNodes[srcNode].push_back(tgtNode);
    }

    int minReorders = 0;

    queue<int> queue; // Stores nodes.
    queue.push(0);

    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        visited[node] = true;

        for (const auto& srcNode : srcNodes[node]) {
            if (!visited[srcNode])
                queue.push(srcNode);
        }

        for (const auto& tgtNode : tgtNodes[node]) {
            if (!visited[tgtNode]) {
                minReorders++;
                queue.push(tgtNode);
            }
        }
    }

    return minReorders;
}

Python

from collections import deque


def find_min_reorders(n: int, connections: list[list[int]]) -> int:
    src_nodes: list[list[int]] = [[] for _ in range(n)]  # Each node's source nodes.
    tgt_nodes: list[list[int]] = [[] for _ in range(n)]  # Each node's target nodes.

    visited: list[bool] = [False] * n

    for src_node, tgt_node in connections:
        src_nodes[tgt_node].append(src_node)
        tgt_nodes[src_node].append(tgt_node)

    min_reorders = 0
    queue: deque[int] = deque([0])  # Stores nodes.

    while queue:
        node = queue.popleft()
        visited[node] = True

        for src_node in src_nodes[node]:
            if not visited[src_node]:
                queue.append(src_node)

        for tgt_node in tgt_nodes[node]:
            if not visited[tgt_node]:
                min_reorders += 1
                queue.append(tgt_node)

    return min_reorders

Every node is visited exactly once, and we also need to track whether each node has been visited.

Both time and space complexity are $O(n)$.