Leetcode1466. 重新规划路线

Every day a Leetcode

题目来源：1466. 重新规划路线

解法1：深度优先搜索

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。

因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。

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

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

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

代码：

/** @lc app=leetcode.cn id=1466 lang=cpp** [1466] 重新规划路线*/// @lc code=start// 深度优先搜索class Solution
{
public:int minReorder(int n, vector<vector<int>> &connections){vector<vector<pair<int, int>>> edges(n);for (vector<int> connection : connections){int from = connection[0], to = connection[1];// 1 表示原树中有一条 a->b 的边edges[from].push_back(pair<int, int>(to, 1));// 0 表示反向边edges[to].push_back(pair<int, int>(from, 0));}function<int(int, int)> dfs = [&](int x, int father) -> int{int res = 0;for (pair<int, int> edge : edges[x])if (edge.first != father){// 原树中有一条 x->edge.first 的边，需要反向if (edge.second == 1)res++;// 递归求解res += dfs(edge.first, x);}return res;};return dfs(0, -1);}
};
// @lc code=end

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(n)，其中 n 是树中节点的数量。

空间复杂度：O(n)，其中 n 是树中节点的数量。建树的空间复杂度为 O(n)，递归所需要的栈空间为 O(n)，因此总的空间复杂度为 O(n)。

解法2：广度优先搜索

代码：

class Solution
{
public:int minReorder(int n, vector<vector<int>> &connections){vector<vector<pair<int, int>>> edges(n);for (vector<int> connection : connections){int from = connection[0], to = connection[1];// 1 表示原树中有一条 a->b 的边edges[from].push_back(pair<int, int>(to, 1));// 0 表示反向边edges[to].push_back(pair<int, int>(from, 0));}queue<int> q;vector<bool> visited(n, false);q.push(0);visited[0] = true;int res = 0;while (!q.empty()){int x = q.front();q.pop();for (pair<int, int> edge : edges[x]){int y = edge.first;if (visited[y] == false){visited[y] = true;q.push(y);if (edge.second == 1)res++;}}}return res;}
};