题解 | 电网维护

题干解析

题设给定我们一个可能具有多个联通分量的无向图，，每个顶点被视作一个电站，针对该图题设要求我们进行一系列操作，操作分为以下两类：

• 一类操作：代码[1, x]

1. 如果设备x在线则记录设备x的编号
2. 如果设备x不在线则记录与设备x相连的联通分量中编号最小的且未下线的一个。

• 二类操作：代码[2, x] 操作效果为将设备x下线。下线操作不影响联通性。

初始时所有设备均在线

算法思路

• DFS：针对所有节点进行DFS操作将所有同一联通分量标号压入最小堆中
• 懒删除：进行二类操作时不直接操作堆中数据，而是使用下线标记数组暂存下线记录，当需要进行一类操作且操作对象为下线时在根据下线记录处理堆顶已下线的节点。
• 模拟：针对操作流程我们无法进行更多的优化，只能模拟。

实现代码

class L3607 {
public:
    vector<int> processQueries(int c, vector<vector<int> > &connections, vector<vector<int> > &queries) {
        vector<vector<int> > G(c + 1);
        for (auto &link: connections) {
            G[link[0]].push_back(link[1]);
            G[link[1]].push_back(link[0]);
        }

        vector belong(c + 1, -1); // 点在那个堆（下标）
        vector<priority_queue<int, vector<int>, greater<>>> heaps;
        priority_queue<int, vector<int>, greater<>> pq; // 暂存

        vector<int> ans;
        vector<bool> offLine(c + 1, false); // 下线标记

        auto dfs = [&](auto &&self, int x) -> void {
            belong[x] = static_cast<int>(heaps.size()); // 记录下标
            pq.push(x); // 压堆
            for (auto next : G[x]) { // 与之相连的也全部压堆
                if (belong[next] < 0) self(self, next);
            }
        };

      	// 全部压堆
        for (int i = 1; i <= c; ++i) {
            if (belong[i] < 0) {
                dfs(dfs, i);
                heaps.emplace_back(move(pq));
            }
        }

      	// 处理请求
        for (auto &q : queries) {
            int tmp = q[1];
          	// 二类请求
            if (q[0] == 2) {
                offLine[tmp] = true;
                continue;
            }
          	// 一类请求——设备在线
            if (!offLine[tmp]) {
                ans.push_back(tmp);
                continue;
            }
          	// 一类请求——设备下线
            auto &h = heaps[belong[tmp]];
            while (!h.empty() && offLine[h.top()]) h.pop();
            ans.push_back(h.empty() ? -1 : h.top());
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：建图阶段，DFS阶段每个节点访问一次，每条边访问一次，共计c + m次，每次压入堆平均耗时，每个节点只压堆一次，总计，操作阶段二类操作，一类操作设备在线时为，下线时均摊复杂度为，最坏单次操作但总体有界，设查询次数为k则操作阶段时间复杂度为，总计，其中c为图中点个数，m为边个数，k为总操作次数
• 空间复杂度：邻接表G空间消耗，堆结构空间消耗，其他辅助数组与临时堆空间消耗，DFS递归调用栈消耗最坏为，总计，其中c为图中点个数，m为边个数