The cheapest node in each group

def sum_of_group_minimums(n, edges, values):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    total = 0
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack, smallest = [s], values[s]     # f = min over the group
        while stack:
            u = stack.pop()
            smallest = min(smallest, values[u])
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
        total += smallest                    # g = sum across groups
    return total

#include <algorithm>
#include <vector>

long long solve(int n, const std::vector<std::vector<int>>& edges, const std::vector<int>& values) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    std::vector<bool> seen(n, false);
    long long total = 0;
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        seen[s] = true;
        std::vector<int> stack{s};
        int smallest = values[s];                    // min over this group
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            smallest = std::min(smallest, values[u]);
            for (int v : adj[u])
                if (!seen[v]) { seen[v] = true; stack.push_back(v); }
        }
        total += smallest;                           // sum across groups
    }
    return total;
}

import java.util.*;

class Solution {
    public long sumOfGroupMinimums(int n, int[][] edges, int[] values) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        long total = 0;
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true;
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            stack.push(s);
            int smallest = values[s];                    // min over this group
            while (!stack.isEmpty()) {
                int u = stack.pop();
                smallest = Math.min(smallest, values[u]);
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; stack.push(v); }
            }
            total += smallest;                           // sum across groups
        }
        return total;
    }
}

function sumOfGroupMinimums(n, edges, values) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const seen = new Array(n).fill(false);
  let total = 0;
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    const stack = [s];
    let smallest = values[s];             // min over this group
    while (stack.length) {
      const u = stack.pop();
      smallest = Math.min(smallest, values[u]);
      for (const v of adj[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
    }
    total += smallest;                    // sum across groups
  }
  return total;
}

fn solve(n: i64, edges: &[[i64; 2]], values: &[i64]) -> i64 {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        let (a, b) = (e[0] as usize, e[1] as usize);
        adj[a].push(b);
        adj[b].push(a);
    }
    let mut seen = vec![false; n];
    let mut total = 0;
    for s in 0..n {
        if seen[s] {
            continue;
        }
        seen[s] = true;
        let mut stack = vec![s];
        let mut smallest = values[s];                    // min over this group
        while let Some(u) = stack.pop() {
            smallest = smallest.min(values[u]);
            for &v in &adj[u] {
                if !seen[v] {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
        total += smallest;                               // sum across groups
    }
    total
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> [Int] -> Int
solve n edges values = go [0 .. n - 1] S.empty 0
  where
    adj = M.fromListWith (++) (concat [[(a, [b]), (b, [a])] | [a, b] <- edges])
    val = M.fromList (zip [0 ..] values)
    go [] _ total = total
    go (s : rest) seen total
      | S.member s seen = go rest seen total
      | otherwise =
          let group = flood [s] (S.singleton s)
          in go rest (S.union seen group) (total + minimum [val M.! v | v <- S.toList group])
    flood [] acc = acc
    flood (u : st) acc =
      let new = [v | v <- M.findWithDefault [] u adj, not (S.member v acc)]
      in flood (new ++ st) (foldr S.insert acc new)