Every day a Leetcode

题目来源：3244. 新增道路查询后的最短距离 II

解法1：贪心

由于题目保证添加的边（捷径）不会交叉，从贪心的角度看，遇到捷径就走捷径是最优的。所有被跳过的城市都不可能再出现在最短路了，直接删除掉。

代码：

/** @lc app=leetcode.cn id=3244 lang=cpp** [3244] 新增道路查询后的最短距离 II*/// @lc code=start
class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){set<int> s; // 存储所有城市的编号// 将每个城市加入到 set 中for (int i = 0; i < n; i++)s.insert(i);vector<int> ans;for (vector<int> &q : queries){// [l, r) 之间的所有城市不可能在最短路里auto l = s.upper_bound(q[0]), r = s.lower_bound(q[1]);s.erase(l, r);// 剩余节点数减 1 即为当前的最短路径长度ans.push_back(s.size() - 1);}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O((n+q)logn)，其中 q 是数组 queries 的长度。

空间复杂度：O(n)。

解法2：并查集

由于题目保证添加的边（捷径）不会交叉，从贪心的角度看，遇到捷径就走捷径是最优的。

把目光放在边上。

用并查集实现边的合并。初始化一个大小为 n−1 的并查集，并查集中的节点 i 表示题目的边 i→(i+1)。（相当于给每条边编号 0,1,2,…n−2。）

连一条从 L 到 R 的边，相当于把并查集中的节点 L,L+1,L+2⋯,R−2 合并到并查集中的节点 R−1 上。

合并的同时，维护并查集连通块个数。

答案就是每次合并后的并查集连通块个数。

// 并查集class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){vector<int> fa(n - 1);iota(fa.begin(), fa.end(), 0);// 非递归并查集auto find = [&](int x) -> int{int rt = x;while (fa[rt] != rt){rt = fa[rt];}while (fa[x] != rt){int tmp = fa[x];fa[x] = rt;x = tmp;}return rt;};vector<int> ans(queries.size());int cnt = n - 1; // 并查集连通块个数for (int qi = 0; qi < queries.size(); qi++){int l = queries[qi][0], r = queries[qi][1] - 1;int fr = find(r);for (int i = find(l); i < r; i = find(i + 1)){fa[i] = fr;cnt--;}ans[qi] = cnt;}return ans;}
};

结果：

复杂度分析：

时间复杂度：O(n+q)，其中 q 是数组 queries 的长度。注意每个点只会被合并一次，在后面的循环中会被 i = find(l) 以及 i = find(i + 1) 跳过。由于数组的特殊性，每次合并的复杂度为 O(1)。

空间复杂度：O(n)。返回值不计入。