当前位置：首页 > 力扣 > 【力扣2846题】图论+二进制提升：高效解决连通性问题（附C++代码）

【力扣2846题】图论+二进制提升：高效解决连通性问题（附C++代码）

2天前

一、题目解读

力扣2846题要求解决一个基于图连通性的操作优化问题。给定一个无向图，包含边权重，以及一系列查询，每个查询询问两点间路径的最小操作次数。题目关键在于高效计算路径上权重分布的统计信息，并转化为操作次数。难点在于处理大量查询时的效率优化，需借助图论算法与数据结构压缩时间复杂度。

二、解题思路

解题思路围绕三个核心：图结构预处理、LCA（最近公共祖先）计算和路径权重统计优化。

1. 图结构预处理：使用邻接表存储边信息，通过DFS遍历记录节点深度及父节点关系，为后续LCA计算做准备。

2. 二进制提升优化LCA：构建父节点表的二进制层次结构，通过位运算快速跳跃至公共祖先，降低查询时间。

3. 路径权重统计：维护每个节点到根的权重计数数组，利用LCA结果合并路径上的权重分布，通过差值计算操作次数。

三、解题步骤

1. 初始化数据结构：创建邻接表adj、父节点表parent、深度depth及权重计数数组cnt。

2. 构建图与预处理：

○ 通过edges构建邻接表，双向存储边信息（节点+权重）。

○ 执行dfs(u, p, d)递归，初始化深度、父节点，并继承父节点的权重计数。

3. 二进制提升预处理：通过位运算生成父节点表的更高层次，支持快速LCA查询。

4. 处理查询：

○ 对每个查询(u, v)，通过LCA找到公共祖先lca。

○ 合并u、v到lca路径的权重计数，计算总权重和最大权重，差值即为操作次数。

四、代码与注释

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    vector<vector<pair<int, int>>> adj; // 邻接表：{节点, 边权}
    vector<vector<int>> parent;         // 二进制提升父节点表
    vector<int> depth;                  // 节点深度
    vector<array<int, 27>> cnt;         // 节点到根的各权重计数
    
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        // 初始化
        adj.resize(n);
        parent.assign(n, vector<int>(20, -1));
        depth.resize(n);
        cnt.resize(n);
        for(auto& e : edges) {
            adj[e[0]].emplace_back(e[1], e[2]);
            adj[e[1]].emplace_back(e[0], e[2]);
        }
        
        // DFS预处理
        dfs(0, -1, 0);
        
        // 二进制提升预处理
        for(int k = 1; k < 20; ++k) {
            for(int u = 0; u < n; ++u) {
                if(parent[u][k-1] != -1) {
                    parent[u][k] = parent[parent[u][k-1]][k-1];
                }
            }
        }
        
        // 处理查询
        vector<int> res;
        for(auto& q : queries) {
            int u = q[0], v = q[1];
            int l = lca(u, v);
            
            // 合并路径上的权重计数
            array<int, 27> total{};
            for(int i = 1; i <= 26; ++i) {
                total[i] = cnt[u][i] + cnt[v][i] - 2 * cnt[l][i];
            }
            
            // 计算操作次数
            int sum = 0, max_cnt = 0;
            for(int i = 1; i <= 26; ++i) {
                sum += total[i];
                max_cnt = max(max_cnt, total[i]);
            }
            res.push_back(sum - max_cnt);
        }
        return res;
    }
    
private:
    void dfs(int u, int p, int d) {
        parent[u][0] = p;
        depth[u] = d;
        if(p != -1) {
            // 继承父节点的计数
            cnt[u] = cnt[p];
            // 更新当前边的权重计数
            for(auto& [v, w] : adj[u]) {
                if(v == p) {
                    cnt[u][w]++;
                    break;
                }
            }
        }
        // 递归处理子节点
        for(auto& [v, w] : adj[u]) {
            if(v != p) dfs(v, u, d+1);
        }
    }
    
    int lca(int u, int v) {
        // 确保u是较深的节点
        if(depth[u] < depth[v]) swap(u, v);
        // 提升u到与v同深度
        for(int k = 19; k >= 0; --k) {
            if(depth[u] - (1 << k) >= depth[v]) {
                u = parent[u][k];
            }
        }
        if(u == v) return u;
        // 同时提升u和v
        for(int k = 19; k >= 0; --k) {
            if(parent[u][k] != -1 && parent[u][k] != parent[v][k]) {
                u = parent[u][k];
                v = parent[v][k];
            }
        }
        return parent[u][0];
    }
};

注释说明：

● adj：邻接表，存储边信息（节点+权重）。

● parent：二进制提升表，通过层次关系快速查找LCA。

● cnt：节点到根的各权重计数，用于路径统计。

● dfs递归函数：初始化深度、父节点及继承权重计数。

● lca(u, v)（代码中未显示，需补充）：通过二进制提升计算公共祖先。