func minimumCost(n int, edges, query [][]int) []int {
type edge struct{ to, w int }
g := make([][]edge, n)
for _, e := range edges {
x, y, w := e[0], e[1], e[2]
g[x] = append(g[x], edge{y, w})
g[y] = append(g[y], edge{x, w})
}
ids := make([]int, n) // 记录每个点所在连通块的编号
for i := range ids {
ids[i] = -1
}
ccAnd := []int{} // 记录每个连通块的边权的 AND
var dfs func(int) int
dfs = func(x int) int {
ids[x] = len(ccAnd) // 记录每个点所在连通块的编号
and := -1
for _, e := range g[x] {
and &= e.w
if ids[e.to] < 0 { // 没有访问过
and &= dfs(e.to)
}
}
return and
}
for i, id := range ids {
if id < 0 { // 没有访问过
ccAnd = append(ccAnd, dfs(i)) // 记录每个连通块的边权的 AND
}
}
ans := make([]int, len(query))
for i, q := range query {
s, t := q[0], q[1]
if s == t {
continue
}
if ids[s] != ids[t] {
ans[i] = -1
} else {
ans[i] = ccAnd[ids[s]]
}
}
return ans
}
func minimumCost(n int, edges, query [][]int) []int {
fa := make([]int, n)
and := make([]int, n)
for i := range fa {
fa[i] = i
and[i] = -1
}
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
for _, e := range edges {
x, y := find(e[0]), find(e[1])
and[y] &= e[2]
if x != y {
and[y] &= and[x]
fa[x] = y
}
}
ans := make([]int, len(query))
for i, q := range query {
s, t := q[0], q[1]
if s == t {
continue
}
if find(s) != find(t) {
ans[i] = -1
} else {
ans[i] = and[find(s)]
}
}
return ans
}
class Solution:
def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
fa = list(range(n))
and_ = [-1] * n
def find(x: int) -> int:
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
for x, y, w in edges:
x = find(x)
y = find(y)
and_[y] &= w
if x != y:
and_[y] &= and_[x]
fa[x] = y
return [0 if s == t else -1 if find(s) != find(t) else and_[find(s)]
for s, t in query]
class Solution:
def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
g = [[] for _ in range(n)]
for x, y, w in edges:
g[x].append((y, w))
g[y].append((x, w))
def dfs(x: int) -> int:
and_ = -1
ids[x] = len(cc_and) # 记录每个点所在连通块的编号
for y, w in g[x]:
and_ &= w
if ids[y] < 0: # 没有访问过
and_ &= dfs(y)
return and_
ids = [-1] * n # 记录每个点所在连通块的编号
cc_and = [] # 记录每个连通块的边权的 AND
for i in range(n):
if ids[i] < 0:
cc_and.append(dfs(i))
return [0 if s == t else -1 if ids[s] != ids[t] else cc_and[ids[s]]
for s, t in query]
class Solution {
public int[] minimumCost(int n, int[][] edges, int[][] query) {
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int[] e : edges) {
int x = e[0], y = e[1], w = e[2];
g[x].add(new int[]{y, w});
g[y].add(new int[]{x, w});
}
int[] ids = new int[n]; // 记录每个点所在连通块的编号
Arrays.fill(ids, -1);
List<Integer> ccAnd = new ArrayList<>(); // 记录每个连通块的边权的 AND
for (int i = 0; i < n; i++) {
if (ids[i] < 0) {
ccAnd.add(dfs(i, ccAnd.size(), g, ids));
}
}
int[] ans = new int[query.length];
for (int i = 0; i < query.length; i++) {
int s = query[i][0], t = query[i][1];
ans[i] = s == t ? 0 : ids[s] != ids[t] ? -1 : ccAnd.get(ids[s]);
}
return ans;
}
private int dfs(int x, int curId, List<int[]>[] g, int[] ids) {
ids[x] = curId; // 记录每个点所在连通块的编号
int and = -1;
for (int[] e : g[x]) {
and &= e[1];
if (ids[e[0]] < 0) { // 没有访问过
and &= dfs(e[0], curId, g, ids);
}
}
return and;
}
}
class Solution {
public int[] minimumCost(int n, int[][] edges, int[][] query) {
int[] fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
int[] and_ = new int[n];
Arrays.fill(and_, -1);
for (int[] e : edges) {
int x = find(e[0], fa);
int y = find(e[1], fa);
and_[y] &= e[2];
if (x != y) {
and_[y] &= and_[x];
fa[x] = y;
}
}
int[] ans = new int[query.length];
for (int i = 0; i < query.length; i++) {
int s = query[i][0], t = query[i][1];
ans[i] = s == t ? 0 : find(s, fa) != find(t, fa) ? -1 : and_[find(s, fa)];
}
return ans;
}
private int find(int x, int[] fa) {
if (fa[x] != x) {
fa[x] = find(fa[x], fa);
}
return fa[x];
}
}
