核心思路与重要公式

关键数学原理

1. 最小生成树性质

切割性质：对于图的任意切割，跨越切割的最小权边必然属于最小生成树。

循环性质：对于图中的任意环，环上权值最大的边一定不在最小生成树中。

2. 查询操作的数学表达

独立性查询的数学定义：

$$\text{Niezalezne}(e_i, e_j) = \begin{cases} >0 & \text{如果 } e_i \text{ 和 } e_j \text{ 无公共端点} \\ \leq 0 & \text{否则} \end{cases} $$

星形查询的数学定义：

$$\text{Gwiazda}(E') = \arg\min_{e \in E'} w(e)$$

其中 $E'$ 是共享公共端点的边集合。

3. 算法核心不等式

在边筛选过程中使用的关键判断：

$$\text{如果 } \text{Niezalezne}(e_i, e_j) > 0 \text{ 且 } w(e_i) < w(e_j) \text{，则保留 } e_i $$

4. 并查集复杂度公式

使用路径压缩和按秩合并的并查集，每次操作的时间复杂度为：

$$O(\alpha(n))$$

其中 $\alpha(n)$ 是反阿克曼函数，增长极其缓慢。

5. 查询次数上界

最坏情况下查询次数上界：

$$\text{总查询次数} = O(m \cdot \log n)$$

其中 $m$ 是边数，$n$ 是顶点数。

算法正确性保证

基于贪心选择性质：每次选择的边都是当前连接不同连通分量的最小权边，这保证了最终得到的是最小生成树。

效率分析公式

设 $k$ 为迭代轮数，则：

• 每轮至少减少一个连通分量：$k \leq n-1$
• 每轮查询次数与当前图的度数分布相关
• 总时间复杂度：$O((n+m)\alpha(n) + Q)$，其中 $Q$ 是查询总次数