1466. Reordered Routes

Reorder Routes to Make All Paths Lead to the City Zero

有点好玩的一道题 问的是在一张有向图上

如何翻转最少数量的边 使得所有点都能访问到第0号城市

已知条件是总共$n$座城市 仅有$n - 1$条边 不会有环

所有点都能访问第0号城市的图长啥样？

肯定是从第0号城市开始搜索时

发现第0号城市连著的边 都是只入第0号城市的

第0号城市不会有任何的出边 而接下来呢：

I. 若第0号城市的入边来自第$i$号城市

第$i$号城市的唯一出边 就是通往第0号城市

因为前面有说此图是$n$个点和$n - 1$条边

因此第$0$号城市必无出边 其他城市皆拥有刚好一条出边

II. 假设第$i$号城市身上的入边来自第$j$号城市

第$j$号城市的唯一出边 就是通往...没错～第$i$号城市

理由和第I点这边说的完全相同逻辑

III. 假设第$j$号城市身上的入边来自第$k$号城市 由此类推...

I、II、III的递归关系

相信各位已经看出来 上述的I、II、III是一个递归关系

不过这个递归关系在本题 未必要用DFS来做

BFS一样能轻松拿捏这边的递归关系

且往下看就知道😁

先暂且忘却原图上边的方向

我们准备一个先进先出的队列

队列起初仅有第0号城市 说明从第0号城市出发

只要队列内还有东西 我们就：

把队首第$i$号城市从队列中取出 标记成已访问

然后看所有与第$i$号城市相连的边

只要这些边上对面的城市$j$还没被访问过

便将城市$j$加入队列中

同时检查一下第$i$号和第$j$号城市之间的边方向

如果方向是从第$i$号城市指向第$j$号城市

体现这条边需要翻转才行 因此翻转计数加1

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

每个点都被访问刚好一遍 都要追踪是否被访问过

因此时间和空间复杂度都是$O(n)$