【每日一题】重新规划路线

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：深度优先搜索
- 方法二：广度优先搜索
写在最后

Tag

【深搜】【广搜】【树】【2023-12-07】

题目来源

1466. 重新规划路线

题目解读

题目给定一张由 n个点（使用 0 到 n−1 编号），n−1 条边构成的有向图，如果忽略边的方向，就变成了一棵树。我们需要改变某些边的方向使得每个点都可以访问到 0 号点。

解题思路

今天是此类有向/无向图问题的第三天，前两天都是无向图的问题，今天看似是有向图的问题，实则是无向图的问题。

如果忽略边的方向，将每条有向边及其反向边加入到图中，那么从任意一点出发都能到达 0 号点。路径上可能会经过反向边，我们需要变更与之对应的原边的方向。需要变更的次数即为答案。

以每个点为起点进行搜索的代价会很大，因此我们考虑从 0 出发去遍历其他点，原来我们需要统计反向边的数量，现在需要统计原方向边的数量。

从 0 出发去遍历其他点有两种方法：

深度优先搜索；
广度优先搜索。

方法一：深度优先搜索

思路

在开始深度优先搜索之前，先根据数组 connections 建立无向图，使用 1 标记原方向的边，用 0 标记反向边。

从 0 开始遍历，访问到某个新的点时，所经过的边被标记为 1 时，就令答案加 1。最终统计得到的答案就是我们需要变更方向的最小路线数。

算法

从编号 0 开始，递归计算需要修改的边数。

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        // 建图
        vector<vector<pair<int, int>>> g(n);
        for (auto connection : connections) {
            int x = connection[0], y = connection[1];
            g[x].push_back(make_pair(y, 1));
            g[y].push_back(make_pair(x, 0));
        }

        function<int(int, int)> dfs = [&](int x, int pa) {
            int res = 0;
            for (auto y : g[x]) {
                if (y.first != pa) {
                    res += y.second + dfs(y.first, x);
                }
            }
            return res;
        };
        return dfs(0, -1);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，建图的时间复杂度为 $O (n)$ ，深搜的时间复杂度也是。

空间复杂度： $O (n)$ ，最坏情况下树退化成一条链，所需栈空间为 $O (n)$ 。

方法二：广度优先搜索

深搜与广搜比较

广度优先搜索与深度优先搜索解题思路一致，都是从节点 0 出发统计到其他节点的反边的数量。深搜是利用递归的方法计算，广搜则利用迭代的方法计算。

深搜中为了保证从 0 向其他节点搜索，给出了 y.first != pa 的限制。广搜中为了防止节点被重复计算，使用了一个数组 vis 来标记已经访问过的节点。

算法

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        // 建图
        vector<vector<pair<int, int>>> g(n);
        for (auto connection : connections) {
            int x = connection[0], y = connection[1];
            g[x].push_back(make_pair(y, 1));
            g[y].push_back(make_pair(x, 0));
        }

        int res = 0;
        vector<int> vis(n);     // 标记节点是否被访问过
        queue<int> q;
        q.push(0);
        vis[0] = 1;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (auto y : g[x]) {
                if (vis[y.first] == 0) {
                    res += y.second;
                    q.push(y.first);
                    vis[y.first] = 1;
                }
            }
        }
        return res;
    }
};