"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", blockquote: "blockquote", code: "code", h2: "h2", li: "li", math: "math", mi: "mi", mrow: "mrow", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.a, { href: "https://leetcode.cn/problems/min-cost-to-connect-all-points/", target: "_blank", rel: "noopener noreferrer", children: "1584. 连接所有点的最小费用" }), "\n一道最小生成树的算法题，适合用于巩固 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "K" }), _jsx(_components.mi, { children: "r" }), _jsx(_components.mi, { children: "u" }), _jsx(_components.mi, { children: "s" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "l" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "Kruskal" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "K" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "r" }), _jsx(_components.span, { className: "mord mathnormal", children: "u" }), _jsx(_components.span, { className: "mord mathnormal", children: "s" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0197em" }, children: "l" })] }) })] }), " 算法。"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "1-代码", children: [_jsx(_components.a, { className: "heading-link", href: "#1-代码", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1. 代码"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 交换两个整数的值（用于按秩合并时的变量交换）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "swap" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " a", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " b", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " tmp ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "a", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token operator", children: "*" }), "a ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "b", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "b ", _jsx(_components.span, { className: "token operator", children: "=" }), " tmp", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 定义边结构体" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " len", _jsx(_components.span, { className: "token punctuation", children: "," }), " x", _jsx(_components.span, { className: "token punctuation", children: "," }), " y", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// len: 边的权重（距离），x 和 y: 边连接的两个点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 排序比较函数：按边长 len 从小到大升序排列" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "cmp" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "void" }), _jsx(_components.span, { className: "token operator", children: "*" }), " a", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "void" }), _jsx(_components.span, { className: "token operator", children: "*" }), " b", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 不允许通过这个指针修改它指向的数" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "a", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "->" }), "len ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "b", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "->" }), "len", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 并查集：查找根节点（包含路径压缩优化，将树的高度降低）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " f", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "==" }), " x ", _jsx(_components.span, { className: "token operator", children: "?" }), " x ", _jsx(_components.span, { className: "token operator", children: ":" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token comment", children: "// f[i] = i 父亲是自己，说明他就是掌门人" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 并查集：合并两个集合" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "unionSet" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " f", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " y", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " fx ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " fy ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " y", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "fx ", _jsx(_components.span, { className: "token operator", children: "==" }), " fy", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 如果已经在同一个集合中，说明连接它们会形成环，返回失败" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 按秩合并优化：始终将较小的树合并到较大的树上" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "swap" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "fy", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+=" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " fx", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 合并成功" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "minCostConnectPoints" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token operator", children: "*" }), " points", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " pointsSize", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " pointsColSize", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " n ", _jsx(_components.span, { className: "token operator", children: "=" }), " pointsSize", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 初始化边集数组：n 个点最多有 n*(n-1)/2 条边" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), " n ", _jsx(_components.span, { className: "token operator", children: "/" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " edgesSize ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第一步：计算所有点对之间的曼哈顿距离，构建完整的边集" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " j ", _jsx(_components.span, { className: "token operator", children: "=" }), " i ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " j", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "x ", _jsx(_components.span, { className: "token operator", children: "=" }), " i", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "y ", _jsx(_components.span, { className: "token operator", children: "=" }), " j", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 曼哈顿距离公式：|x1 - x2| + |y1 - y2|" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "len ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "abs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "abs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第二步：将所有边按距离从小到大排序（贪心策略的核心）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "qsort" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "edges", _jsx(_components.span, { className: "token punctuation", children: "," }), " edgesSize", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " cmp", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第三步：并查集初始化" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " i", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始时每个点的父节点是它自己" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始秩（集合大小）为 1" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " ret ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 累计最小生成树的总权重" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " num ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 记录当前已连接的点数（当连通点数等于 n 时，边数为 n-1）" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第四步：遍历排序后的边，依次尝试加入" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " edgesSize", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 如果这条边连接了两个尚未连通的集合" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token function", children: "unionSet" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " rank", _jsx(_components.span, { className: "token punctuation", children: "," }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "x", _jsx(_components.span, { className: "token punctuation", children: "," }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "y", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ret ", _jsx(_components.span, { className: "token operator", children: "+=" }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "len", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 记录权重" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" num", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 增加已连接的点数" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "num ", _jsx(_components.span, { className: "token operator", children: "==" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 优化：如果所有点都已连通，提前结束" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "break" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ret", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "下面进行拆解。" }), "\n"] }), "\n", _jsxs(_components.h2, { id: "2-工具函数", children: [_jsx(_components.a, { className: "heading-link", href: "#2-工具函数", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2. 工具函数"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 交换两个整数的值（用于按秩合并时的变量交换）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "swap" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " a", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " b", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " tmp ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "a", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token operator", children: "*" }), "a ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "b", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "b ", _jsx(_components.span, { className: "token operator", children: "=" }), " tmp", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 定义边结构体" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " len", _jsx(_components.span, { className: "token punctuation", children: "," }), " x", _jsx(_components.span, { className: "token punctuation", children: "," }), " y", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// len: 边的权重（距离），x 和 y: 边连接的两个点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 排序比较函数：按边长 len 从小到大升序排列" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "cmp" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "void" }), _jsx(_components.span, { className: "token operator", children: "*" }), " a", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "void" }), _jsx(_components.span, { className: "token operator", children: "*" }), " b", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 不允许通过这个指针修改它指向的数" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "a", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "->" }), "len ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "b", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "->" }), "len", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.h2, { id: "3-并查集", children: [_jsx(_components.a, { className: "heading-link", href: "#3-并查集", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "3. 并查集"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 并查集：查找根节点（包含路径压缩优化，将树的高度降低）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " f", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "==" }), " x ", _jsx(_components.span, { className: "token operator", children: "?" }), " x ", _jsx(_components.span, { className: "token operator", children: ":" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 并查集：合并两个集合" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "unionSet" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " f", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " y", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " fx ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " fy ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "find" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " y", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "fx ", _jsx(_components.span, { className: "token operator", children: "==" }), " fy", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 如果已经在同一个集合中，说明连接它们会形成环，返回失败" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 按秩合并优化：始终将较小的树合并到较大的树上" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "swap" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "fy", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fx", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+=" }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "fy", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " fx", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 合并成功" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" })] }) }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "f[]" }), " 是一个集合。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "f[i]" }), " 表示节点的父亲，如果 ", _jsx(_components.code, { className: "language-auto", children: "f[i] = i" }), "，也就是父亲为自己，说明没有父亲，此时 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 是根结点。"] }), "\n", _jsxs(_components.li, { children: ["路径压缩的关键代码：", _jsx(_components.code, { className: "language-auto", children: "f[x] = find(f, f[x])" }), "。"] }), "\n", _jsxs(_components.li, { children: ["并查集的合并在王道书上有讲过，见 ", _jsx(_components.a, { href: "/5_DataStructure/%E7%8E%8B%E9%81%93%E7%AC%94%E8%AE%B0%F0%9F%93%92/%E3%80%90%E7%AC%AC%E5%85%AD%E7%AB%A0%E3%80%91%E5%9B%BE", className: "internal", "data-fs-resolved-file-path": "/5_DataStructure/王道笔记📒/【第六章】图.md", children: "【第六章】图" }), "的 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "K" }), _jsx(_components.mi, { children: "r" }), _jsx(_components.mi, { children: "u" }), _jsx(_components.mi, { children: "s" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "l" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "Kruskal" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "K" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "r" }), _jsx(_components.span, { className: "mord mathnormal", children: "u" }), _jsx(_components.span, { className: "mord mathnormal", children: "s" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0197em" }, children: "l" })] }) })] }), " 算法部分。"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "4-主程序", children: [_jsx(_components.a, { className: "heading-link", href: "#4-主程序", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "4. 主程序"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "minCostConnectPoints" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token operator", children: "*" }), " points", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " pointsSize", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " pointsColSize", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " n ", _jsx(_components.span, { className: "token operator", children: "=" }), " pointsSize", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 初始化边集数组：n 个点最多有 n*(n-1)/2 条边" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), " n ", _jsx(_components.span, { className: "token operator", children: "/" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " edgesSize ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第一步：计算所有点对之间的曼哈顿距离，构建完整的边集" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " j ", _jsx(_components.span, { className: "token operator", children: "=" }), " i ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " j", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "x ", _jsx(_components.span, { className: "token operator", children: "=" }), " i", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "y ", _jsx(_components.span, { className: "token operator", children: "=" }), " j", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 曼哈顿距离公式：|x1 - x2| + |y1 - y2|" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "edgesSize", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "len ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "abs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "abs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " points", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第二步：将所有边按距离从小到大排序（贪心策略的核心）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "qsort" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "edges", _jsx(_components.span, { className: "token punctuation", children: "," }), " edgesSize", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Edge" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " cmp", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第三步：并查集初始化" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" f", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " i", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始时每个点的父节点是它自己" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rank", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始秩（集合大小）为 1" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " ret ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 累计最小生成树的总权重" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " num ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 记录当前已连接的点数（当连通点数等于 n 时，边数为 n-1）" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 第四步：遍历排序后的边，依次尝试加入" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " edgesSize", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 如果这条边连接了两个尚未连通的集合" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token function", children: "unionSet" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "f", _jsx(_components.span, { className: "token punctuation", children: "," }), " rank", _jsx(_components.span, { className: "token punctuation", children: "," }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "x", _jsx(_components.span, { className: "token punctuation", children: "," }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "y", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ret ", _jsx(_components.span, { className: "token operator", children: "+=" }), " edges", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), "len", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 记录权重" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" num", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 增加已连接的点数" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "num ", _jsx(_components.span, { className: "token operator", children: "==" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 优化：如果所有点都已连通，提前结束" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "break" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ret", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };