Visit the website for the full story and full puzzle description.

I decided to go with two implementations of Kruskal's algorithm, as part one and two are different enough. I didn't use a disjoint set representation. It's fast enough this way as well, and switching to disjoint sets would just make the code longer.

This is how my graph looks with the spanning tree:

I created a small renderer for this. (Well, ChatGPT created the render, with my guidance.)

namespace AdventOfCode.Y2025.Day08;

using System.Collections.Generic;
using System.Data;
using System.Linq;

record Point(decimal x, decimal y, decimal z);

[ProblemName("Playground")]
class Solution : Solver {

    public object PartOne(string input) {
        // Apply 1000 steps of Kruskal's algorithm to the points using the specified
        // metric, then return the product of the sizes of the three largest components.
        var points = Parse(input);
        var setOf = points.ToDictionary(p => p, p => new HashSet<Point>([p]));
        foreach (var (a, b) in GetOrderedPairs(points).Take(1000)) {
            if (setOf[a] != setOf[b]) {
                Connect(a, b, setOf);
            }
        }
        return setOf.Values.Distinct()
            .OrderByDescending(set => set.Count)
            .Take(3)
            .Aggregate(1, (a, b) => a * b.Count);
    }

    public object PartTwo(string input) {
        // Run Kruskal's algorithm on all points and return the product of the
        // x-coordinates of the last edge added to the spanning tree.
        var points = Parse(input);
        var componentCount = points.Length;
        var setOf = points.ToDictionary(p => p, p => new HashSet<Point>([p]));
        var res = 0m;
        foreach (var (a, b) in GetOrderedPairs(points).TakeWhile(_ => componentCount > 1)) {
            if (setOf[a] != setOf[b]) {
                Connect(a, b, setOf);
                res = a.x * b.x;
                componentCount--;
            }
        }
        return res;
    }

    void Connect(Point a, Point b, Dictionary<Point, HashSet<Point>> setOf) {
        setOf[a].UnionWith(setOf[b]);
        foreach (var p in setOf[b]) {
            setOf[p] = setOf[a];
        }
    }

    IEnumerable<(Point a, Point b)> GetOrderedPairs(Point[] points) =>
        from a in points
        from b in points
        where (a.x, a.y, a.z).CompareTo((b.x, b.y, b.z)) < 0
        orderby Metric(a,b)
        select (a, b);

    decimal Metric(Point a, Point b) =>
        (a.x - b.x) * (a.x - b.x) +
        (a.y - b.y) * (a.y - b.y) +
        (a.z - b.z) * (a.z - b.z);

    Point[] Parse(string input) => (
        from line in input.Split("\n")
        let parts = line.Split(",").Select(int.Parse).ToArray()
        select new Point(parts[0], parts[1], parts[2])
    ).ToArray();
}

Please ☆ my repo if you like it!