算法笔记：并查集、Kruskal、LCA

一、并查集（Disjoint Set Union, DSU）

核心原理

• 功能：管理元素分组，支持两种操作：
• Find：查询元素所属集合
• Union：合并两个集合
• 优化：
• 路径压缩（find函数）：使树结构扁平化，降低查询复杂度至接近 O(1)

代码解析

int fa[N], cnt[N]; // fa:父节点数组 cnt:集合大小数组

int find(int x) {  // 路径压缩
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 初始化
for(int i=1; i<=n; i++) fa[i] = i, cnt[i] = 1;

// 合并操作（z=1）
int fx = find(x), fy = find(y);
if(fx != fy) {
    fa[fx] = fy;
    cnt[fy] += cnt[fx];  // 维护集合大小
}

// 查询连通性（z=2）
cout << (find(x) == find(y) ? "Y\n" : "N\n");

// 查询集合大小（z=3）
cout << cnt[find(x)] << "\n";

二、Kruskal 算法（最小生成树）

核心原理

• 目标：在带权图中找到权值和最小的生成树
• 步骤：
• 将所有边按权值升序排序
• 依次选择边，若两端点不连通则合并集合
• 当选边数为 n-1 时终止（树的性质）

代码解析

vector<pair<int, pair<int, int>>> edge; // {权重, {u, v}}
sort(edge.begin(), edge.end());         // 按权值排序

int ans = 0, cnt_m = 0;
for(auto e : edge) {
    int u = e.second.first, v = e.second.second;
    int fx = find(u), fy = find(v);
    if(fx != fy) {
        ans += e.first;
        fa[fx] = fy;
        cnt_m++;
        if(cnt_m == n-1) break;  // 已形成生成树
    }
}

if(cnt_m != n-1) cout << "orz";  // 图不连通
else cout << ans;

三、LCA（最近公共祖先）倍增算法

核心原理

• 预处理：
• DFS：记录每个节点的深度（dep数组）和直接父节点（fa数组）
• 倍增表：dp[i][j] 表示节点 i 向上跳 2^j 步的祖先节点
• 查询步骤：
• 调整深度：将较深节点向上跳至与较浅节点同深度
• 同步上跳：从最大步长开始试探，寻找首个公共祖先

代码解析

// DFS预处理深度和父节点
void dfs(int x, int pre) {
    dep[x] = dep[pre] + 1;
    fa[x] = pre;
    for(int v : to[x]) {
        if(v != pre) dfs(v, x);
    }
}

// 构建倍增表
for(int j=0; j<=20; j++) {
    if(j == 0) {
        for(int x=1; x<=n; x++) dp[x][j] = fa[x];
    } else {
        for(int x=1; x<=n; x++) {
            dp[x][j] = dp[dp[x][j-1]][j-1];
        }
    }
}

// LCA查询函数
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    // 调整深度
    for(int j=20; j>=0; j--) {
        if(dep[x] - (1<<j) >= dep[y]) {
            x = dp[x][j];
        }
    }
    // 同步上跳
    for(int j=20; j>=0; j--) {
        if(dp[x][j] != dp[y][j]) {
            x = dp[x][j];
            y = dp[y][j];
        }
    }
    return x == y ? x : fa[x];
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com