Árboles de expansión mínima

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;
 
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
 
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }
 
		if (sizes[x_root] < sizes[y_root]) { std::swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}
 
	bool connected(int x, int y) { return find(x) == find(y); }
};
// EndCodeSnip
 
int main() {
	int city_num;
	int road_num;
	std::cin >> city_num >> road_num;
 
	struct Road {
		int c1, c2;
		int cost;
	};
	vector<Road> roads(road_num);
	for (Road &r : roads) {
		std::cin >> r.c1 >> r.c2 >> r.cost;
		r.c1--;
		r.c2--;
	}
	std::sort(roads.begin(), roads.end(),
	          [&](const Road &e1, const Road &e2) { return e1.cost < e2.cost; });
 
	DisjointSets cities(city_num);
	long long min_cost = 0;
	int added = 0;
	for (Road &r : roads) {
		bool status = cities.unite(r.c1, r.c2);
		min_cost += status * r.cost;
		added += status;
	}
 
	if (added != city_num - 1) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		cout << min_cost << endl;
	}
}

import java.io.*;
import java.util.*;
 
public class RoadReparation {
	// BeginCodeSnip{Road Class}
	static class Road {
		int c1, c2;
		int cost;
 
		public Road(int c1, int c2, int cost) {
			this.c1 = c1;
			this.c2 = c2;
			this.cost = cost;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int cityNum = Integer.parseInt(initial.nextToken());
		int roadNum = Integer.parseInt(initial.nextToken());
 
		Road[] roads = new Road[roadNum];
		for (int r = 0; r < roadNum; r++) {
			StringTokenizer road = new StringTokenizer(read.readLine());
			roads[r] = new Road(Integer.parseInt(road.nextToken()) - 1,
			                    Integer.parseInt(road.nextToken()) - 1,
			                    Integer.parseInt(road.nextToken()));
		}
		Arrays.sort(roads, Comparator.comparingInt(r -> r.cost));
 
		DisjointSets cities = new DisjointSets(cityNum);
		long minCost = 0;
		int added = 0;
		for (Road r : roads) {
			int status = cities.unite(r.c1, r.c2) ? 1 : 0;
			minCost += status * r.cost;
			added += status;
		}
 
		if (added != cityNum - 1) {
			System.out.println("IMPOSSIBLE");
		} else {
			System.out.println(minCost);
		}
	}
}
 
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
	int[] parents;
	int[] sizes;
 
	public DisjointSets(int size) {
		parents = new int[size];
		sizes = new int[size];
		for (int i = 0; i < size; i++) {
			parents[i] = i;
			sizes[i] = -1;
		}
	}
 
	/** @return el nodo "representante" de la componente de x */
	public int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}
 
	/** @return si la fusión cambió la conectividad */
	public boolean unite(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) { return false; }
 
		if (sizes[xRoot] < sizes[yRoot]) { return unite(yRoot, xRoot); }
		parents[yRoot] = xRoot;
		sizes[xRoot] += sizes[yRoot];
		return true;
	}
 
	/** @return si x e y están en la misma componente conexa */
	public boolean connected(int x, int y) { return find(x) == find(y); }
}
// EndCodeSnip

# BeginCodeSnip{DSU (from the module)}
class DisjointSets:
	def __init__(self, size: int) -> None:
		self.parents = [i for i in range(size)]
		self.sizes = [1 for _ in range(size)]
 
	def find(self, x: int) -> int:
		if self.parents[x] == x:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]
 
	def unite(self, x: int, y: int) -> bool:
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return False
 
		if self.sizes[x_root] < self.sizes[y_root]:
			x_root, y_root = y_root, x_root
 
		self.parents[y_root] = x_root
		self.sizes[x_root] += self.sizes[y_root]
		return True
 
	def connected(self, x: int, y: int) -> bool:
		return self.find(x) == self.find(y)
 
 
# EndCodeSnip
 
 
city_num, road_num = map(int, input().split())
roads = []
for _ in range(road_num):
	a, b, cost = map(int, input().split())
	roads.append((cost, a - 1, b - 1))
roads.sort()
 
cities = DisjointSets(city_num)
min_cost = 0
added = 0
for cost, c1, c2 in roads:
	status = cities.unite(c1, c2)
	min_cost += status * cost
	added += status
 
print("IMPOSSIBLE" if added != city_num - 1 else min_cost)

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
long long prim(const vector<vector<pair<int, int>>> &neighbors) {
	const int n = neighbors.size();  // solo una abreviatura
 
	long long min_cost = 0;
	vector<long long> dist(n, std::numeric_limits<long long>().max());
	dist[0] = 0;
	std::priority_queue<pair<long long, int>> q;
	q.push({0, 0});
	vector<bool> visited(n);
	int added = 0;
	while (added < n) {
		if (q.empty()) { return -1; }
		auto [curr_cost, v] = q.top();
		q.pop();
		curr_cost *= -1;
		if (dist[v] < curr_cost) { continue; }
 
		added++;
		visited[v] = true;
		min_cost += curr_cost;
		for (auto &[next, n_cost] : neighbors[v]) {
			if (!visited[next] && n_cost < dist[next]) {
				dist[next] = n_cost;
				q.push({-n_cost, next});
			}
		}
	}
 
	return min_cost;
}
 
int main() {
	int city_num;
	int road_num;
	std::cin >> city_num >> road_num;
 
	vector<vector<pair<int, int>>> neighbors(city_num);
	for (int r = 0; r < road_num; r++) {
		int a, b;
		int cost;
		std::cin >> a >> b >> cost;
		neighbors[--a].push_back({--b, cost});
		neighbors[b].push_back({a, cost});
	}
 
	long long min_cost = prim(neighbors);
	if (min_cost == -1) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		cout << min_cost << endl;
	}
}

import java.io.*;
import java.util.*;
 
public class RoadReparation {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int cityNum = Integer.parseInt(initial.nextToken());
		int roadNum = Integer.parseInt(initial.nextToken());
 
		List<int[]>[] neighbors = new ArrayList[cityNum];
		for (int c = 0; c < cityNum; c++) { neighbors[c] = new ArrayList<>(); }
		for (int r = 0; r < roadNum; r++) {
			StringTokenizer road = new StringTokenizer(read.readLine());
			int a = Integer.parseInt(road.nextToken()) - 1;
			int b = Integer.parseInt(road.nextToken()) - 1;
			int cost = Integer.parseInt(road.nextToken());
			neighbors[a].add(new int[] {b, cost});
			neighbors[b].add(new int[] {a, cost});
		}
 
		long minCost = prim(neighbors);
		if (minCost == -1) {
			System.out.println("IMPOSSIBLE");
		} else {
			System.out.println(minCost);
		}
	}
 
	static long prim(List<int[]>[] neighbors) {
		final int n = neighbors.length;  // solo una abreviatura
 
		long minCost = 0;
		long[] dist = new long[n];
		Arrays.fill(dist, Long.MAX_VALUE);
		dist[0] = 0;
		PriorityQueue<LongIntPair> q = new PriorityQueue<>();  // {cost, vertex}
		q.add(new LongIntPair(0, 0));
		boolean[] visited = new boolean[n];
		int added = 0;
		while (added < n) {
			if (q.isEmpty()) { return -1; }
 
			LongIntPair curr = q.poll();
			if (dist[curr.second] < curr.first) { continue; }
 
			added++;
			visited[curr.second] = true;
			minCost += curr.first;
			for (int[] next : neighbors[curr.second]) {
				if (!visited[next[0]] && next[1] < dist[next[0]]) {
					dist[next[0]] = next[1];
					q.add(new LongIntPair(next[1], next[0]));
				}
			}
		}
 
		return minCost;
	}
}
 
class LongIntPair implements Comparable<LongIntPair> {
	long first;
	int second;
 
	public LongIntPair(long first, int second) {
		this.first = first;
		this.second = second;
	}
 
	@Override
	public int compareTo(LongIntPair other) {
		if (first != other.first) { return (int)(first - other.first); }
		return second - other.second;
	}
}

from typing import List, Tuple
import heapq
 
 
def prim(neighbors: List[Tuple[int, int]]) -> int:
	n = len(neighbors)  # solo una abreviatura
 
	min_cost = 0
	dist = [float("inf") for _ in range(n)]
	dist[0] = 0
	q = [(0, 0)]
	visited = [False for _ in range(n)]
	added = 0
	while added < n:
		if not q:
			return -1
 
		curr_cost, v = heapq.heappop(q)
		if dist[v] < curr_cost:
			continue
 
		added += 1
		visited[v] = True
		min_cost += curr_cost
		for next_, n_cost in neighbors[v]:
			if not visited[next_] and n_cost < dist[next_]:
				dist[next_] = n_cost
				heapq.heappush(q, (n_cost, next_))
	return min_cost
 
 
city_num, road_num = map(int, input().split())
neighbors = [[] for _ in range(city_num)]
for _ in range(road_num):
	a, b, cost = map(int, input().split())
	a -= 1
	b -= 1
	neighbors[a].append((b, cost))
	neighbors[b].append((a, cost))
 
 
min_cost = prim(neighbors)
print("IMPOSSIBLE" if min_cost == -1 else min_cost)