生成树与树形图

def min_cost_connect(points: list[list[int]]) -> int:
    """Minimum spanning tree weight of all points under Manhattan distance (LC 1584)."""
    n = len(points)
    dist = [float("inf")] * n  # dist[v]: cheapest edge from the tree to v so far
    dist[0] = 0
    in_tree = [False] * n
    total = 0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=lambda v: dist[v])  # nearest outside node
        in_tree[u] = True
        total += dist[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                dist[v] = min(dist[v], d)
    return total

// Minimum spanning tree weight of all points under Manhattan distance (LC 1584).
long long minCostConnect(const vector<pair<int, int>>& points) {
    int n = points.size();
    vector<long long> dist(n, LLONG_MAX);  // dist[v]: cheapest edge from the tree to v so far
    dist[0] = 0;
    vector<bool> inTree(n, false);
    long long total = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int v = 0; v < n; v++)  // nearest outside node
            if (!inTree[v] && (u < 0 || dist[v] < dist[u])) u = v;
        inTree[u] = true;
        total += dist[u];
        for (int v = 0; v < n; v++)
            if (!inTree[v]) {
                long long d = abs(points[u].first - points[v].first) + abs(points[u].second - points[v].second);
                dist[v] = min(dist[v], d);
            }
    }
    return total;
}

class Solution {
    // Minimum spanning tree weight of all points under Manhattan distance (LC 1584).
    long minCostConnect(int[][] points) {
        int n = points.length;
        long[] dist = new long[n]; // dist[v]: cheapest edge from the tree to v so far
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        boolean[] inTree = new boolean[n];
        long total = 0;
        for (int round = 0; round < n; round++) {
            int u = -1;
            for (int v = 0; v < n; v++) // nearest outside node
                if (!inTree[v] && (u < 0 || dist[v] < dist[u])) u = v;
            inTree[u] = true;
            total += dist[u];
            for (int v = 0; v < n; v++)
                if (!inTree[v]) {
                    long d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                    dist[v] = Math.min(dist[v], d);
                }
        }
        return total;
    }
}

// minCostConnect returns the minimum spanning tree weight of all points under Manhattan distance.
func minCostConnect(points [][2]int) int {
	n := len(points)
	abs := func(x int) int {
		if x < 0 {
			return -x
		}
		return x
	}
	dist := make([]int, n) // dist[v]: cheapest edge from the tree to v so far
	for v := 1; v < n; v++ {
		dist[v] = 1 << 62
	}
	inTree := make([]bool, n)
	total := 0
	for round := 0; round < n; round++ {
		u := -1
		for v := 0; v < n; v++ { // nearest outside node
			if !inTree[v] && (u < 0 || dist[v] < dist[u]) {
				u = v
			}
		}
		inTree[u] = true
		total += dist[u]
		for v := 0; v < n; v++ {
			if !inTree[v] {
				d := abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
				dist[v] = min(dist[v], d)
			}
		}
	}
	return total
}

def min_height_roots(n: int, edges: list[list[int]]) -> list[int]:
    """Roots giving the tree its minimum height (LC 310): the 1 or 2 nodes left after peeling leaves."""
    if n <= 2:
        return list(range(n))
    graph = [[] for _ in range(n)]
    deg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        deg[u] += 1
        deg[v] += 1
    leaves = [u for u in range(n) if deg[u] == 1]
    left = n
    while left > 2:  # peel one whole layer of leaves at a time
        left -= len(leaves)
        nxt = []
        for leaf in leaves:
            for nb in graph[leaf]:
                deg[nb] -= 1
                if deg[nb] == 1:  # nb just became a leaf of the smaller tree
                    nxt.append(nb)
        leaves = nxt
    return sorted(leaves)

// Roots giving the tree its minimum height (LC 310): the 1 or 2 nodes left after peeling leaves.
vector<int> minHeightRoots(int n, const vector<pair<int, int>>& edges) {
    if (n <= 2) {
        vector<int> all(n);
        iota(all.begin(), all.end(), 0);
        return all;
    }
    vector<vector<int>> graph(n);
    vector<int> deg(n, 0), leaves;
    for (auto [u, v] : edges) {
        graph[u].push_back(v);
        graph[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    for (int u = 0; u < n; u++)
        if (deg[u] == 1) leaves.push_back(u);
    for (int left = n; left > 2;) {  // peel one whole layer of leaves at a time
        left -= leaves.size();
        vector<int> next;
        for (int leaf : leaves)
            for (int nb : graph[leaf])
                if (--deg[nb] == 1) next.push_back(nb);  // nb just became a leaf of the smaller tree
        leaves = next;
    }
    sort(leaves.begin(), leaves.end());
    return leaves;
}

class Solution {
    // Roots giving the tree its minimum height (LC 310): the 1 or 2 nodes left after peeling leaves.
    List<Integer> minHeightRoots(int n, int[][] edges) {
        List<Integer> leaves = new ArrayList<>();
        if (n <= 2) {
            for (int u = 0; u < n; u++) leaves.add(u);
            return leaves;
        }
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] deg = new int[n];
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
            deg[e[0]]++;
            deg[e[1]]++;
        }
        for (int u = 0; u < n; u++)
            if (deg[u] == 1) leaves.add(u);
        for (int left = n; left > 2;) { // peel one whole layer of leaves at a time
            left -= leaves.size();
            List<Integer> next = new ArrayList<>();
            for (int leaf : leaves)
                for (int nb : graph.get(leaf))
                    if (--deg[nb] == 1) next.add(nb); // nb just became a leaf of the smaller tree
            leaves = next;
        }
        Collections.sort(leaves);
        return leaves;
    }
}

import "sort"

// minHeightRoots returns the roots giving the tree its minimum height (LC 310).
func minHeightRoots(n int, edges [][2]int) []int {
	if n <= 2 {
		all := make([]int, n)
		for i := range all {
			all[i] = i
		}
		return all
	}
	graph := make([][]int, n)
	deg := make([]int, n)
	for _, e := range edges {
		graph[e[0]] = append(graph[e[0]], e[1])
		graph[e[1]] = append(graph[e[1]], e[0])
		deg[e[0]]++
		deg[e[1]]++
	}
	var leaves []int
	for u := 0; u < n; u++ {
		if deg[u] == 1 {
			leaves = append(leaves, u)
		}
	}
	for left := n; left > 2; { // peel one whole layer of leaves at a time
		left -= len(leaves)
		var next []int
		for _, leaf := range leaves {
			for _, nb := range graph[leaf] {
				deg[nb]--
				if deg[nb] == 1 { // nb just became a leaf of the smaller tree
					next = append(next, nb)
				}
			}
		}
		leaves = next
	}
	sort.Ints(leaves)
	return leaves
}