题目描述
给你一个 n
个节点的带权无向图,节点编号为 0
到 n - 1
。
给你一个整数 n
和一个数组 edges
,其中 edges[i] = [u_i, v_i, w_i]
表示节点 u_i
和 v_i
之间有一条权值为 w_i
的无向边。
在图中,一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点,且图中存在连接旅途中相邻节点的边。注意,一趟旅途可能访问同一条边或者同一个节点多次。
如果旅途开始于节点 u
,结束于节点 v
,我们定义这一趟旅途的 代价 是经过的边权按位与 AND
的结果。换句话说,如果经过的边对应的边权为 w_0, w_1, w_2, ..., w_k
,那么代价为 w_0 & w_1 & w_2 & ... & w_k
,其中 &
表示按位与 AND
操作。
给你一个二维数组 query
,其中 query[i] = [s_i, t_i]
。对于每一个查询,你需要找出从节点开始 s_i
,在节点 t_i
处结束的旅途的最小代价。如果不存在这样的旅途,答案为 -1
。
返回数组 answer
,其中 answer[i]
表示对于查询 i
的 最小 旅途代价。
样例
输入:n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
输出:[1,-1]
解释:
第一个查询想要得到代价为 1 的旅途,我们依次访问:
0->1(边权为 7 )1->2 (边权为 1 )2->1(边权为 1 )1->3 (边权为 7 )。
第二个查询中,无法从节点 3 到节点 4,所以答案为 -1。
输入:n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
输出:[0]
解释:
第一个查询想要得到代价为 0 的旅途,我们依次访问:
1->2(边权为 1 ),2->1(边权 为 6 ),1->2(边权为 1 )。
限制
1 <= n <= 10^5
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= w_i <= 10^5
1 <= query.length <= 10^5
query[i].length == 2
0 <= s_i, t_i <= n - 1
算法
(并查集) $O(n + m + q)$
- 注意到,如果两个点在一个连通块,则这两个点之间的最短代价必定是经过了连通块所有的边之后得到的。这是因为
AND
操作会使结果越来越小。 - 维护一个并查集,记录每个连通块中所有边的
AND
值。 - 遍历每条边,插入到并查集。
- 对于每个询问,如果两个点不在同一个连通块,则返回 $-1$,否则返回连通块的
AND
值。
时间复杂度
- 假设并查集单次插入和查找操作时间为常数。
- 初始化并查集的时间复杂度为 $O(n)$。
- 插入并查集的时间复杂度为 $O(m)$。
- 每个询问仅需要常数的时间得到答案。
- 故总时间复杂度为 $O(n + m + q)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储并查集。
C++ 代码
class Solution {
private:
vector<int> f, sz, w;
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x, int y, int z) {
int fx = find(x), fy = find(y);
if (fx == fy) {
w[fx] &= z;
return;
}
if (sz[fx] < sz[fy]) {
f[fx] = fy;
sz[fy] += sz[fx];
w[fy] = w[fy] & w[fx] & z;
} else {
f[fy] = fx;
sz[fx] += sz[fy];
w[fx] = w[fx] & w[fy] & z;
}
}
public:
vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
f.resize(n); sz.resize(n), w.resize(n);
for (int i = 0; i < n; i++) {
f[i] = i;
sz[i] = 1;
w[i] = (1 << 17) - 1;
}
for (const auto &e : edges)
merge(e[0], e[1], e[2]);
const int q = query.size();
vector<int> ans(q);
for (int i = 0; i < q; i++) {
if (query[i][0] == query[i][1]) {
ans[i] = 0;
continue;
}
int fx = find(query[i][0]), fy = find(query[i][1]);
ans[i] = fx == fy ? w[fx] : -1;
}
return ans;
}
};