3607. 電網維護

思路

題目會有兩種操作，第一個操作（維護）分為三種情況:

1. 要維護的機器target自己運作中，target即為所求。
2. target沒有在運作，需要找跟自己有連接的最小機器（運作中）幫助維護。
3. 跟自己連接的機器全都沒有在運作，無法維護，答案-1。 第二個操作單純把某編號的機器關掉。

因為需要找到「跟自己有連接的最小機器」，所以需要紀錄跟自己連接在一起的機器有哪些。
因此使用並查集去將機器連接在一起，連接完畢之後用 set 或是 heap 紀錄下來，供後續查找使用。

程式碼

1. 並查集 + 有序集合

class Solution {
private:
    vector<int> parent;
    int find_parent(int x) {
        if(parent[x] != x) {
            parent[x] = find_parent(parent[x]);
        }
        return parent[x];
    }
public:
    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        parent.resize(c + 1);
        iota(parent.begin(), parent.end(), 0);
        for(auto& vec : connections) {
            int rootX = find_parent(vec[0]);
            int rootY = find_parent(vec[1]);
            if(rootX < rootY) {
                parent[rootY] = rootX;
            }
            else {
                parent[rootX] = rootY;
            }
        }
        unordered_map<int, set<int>> umap;
        vector<int> res;
        for(int i = 1; i <= c; ++i) {
            umap[find_parent(i)].insert(i);
        }
        for(auto& q : queries) {
            int type = q[0], target = q[1];
            if(type == 1) {
                if(umap[parent[target]].find(target) != umap[parent[target]].end()) { // 自己存在
                    res.push_back(target);
                }
                else { // 自己不存在
                    if(umap[parent[target]].size()) { // 有人存在
                        res.push_back(*umap[parent[target]].begin());
                    }
                    else { // 沒有人存在, 嗚嗚嗚
                        res.push_back(-1);
                    }
                }
            }
            else {
                umap[parent[target]].erase(target);
            }
        }
        return res;
    }
};

2. 深度優先搜索 + 懶刪除堆 (友人提供)

class Solution {
public:
    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        vector<int> ans;
        vector<vector<int>> link(c); // 自己的鄰居
        for(auto& v : connections) {
            link[v[0]-1].push_back(v[1]-1);
            link[v[1]-1].push_back(v[0]-1);
        }
        vector<int> findset(c, -1); // parent;
        vector<bool> power(c, true); // 有沒有能量
        unordered_map<int, priority_queue<int, vector<int>, greater<>>> umap;
        int index = 0;
        auto dfs = [&](this auto&& dfs, int v1) -> void {
            findset[v1] = index;
            umap[index].push(v1);
            for(int j : link[v1]){
                if(findset[j]<0)
                    dfs(j);
            }
        };
        // 分組。
        for(int i=0; i<c; i++){
            if(findset[i]!=-1) continue; // 已經被加過了
            for(int j:link[i]){
                dfs(j);
            }
            findset[i] = index;
            umap[index].push(i);
            index++;
        }
        for(auto& v:queries){
            if(v[0]==2)
                power[v[1]-1] = false;
            else{
                if(power[v[1]-1])
                    ans.push_back(v[1]);
                else{
                    auto& temp = umap[findset[v[1]-1]];
                    while(!temp.empty()){
                        if(power[temp.top()]){
                            ans.push_back(temp.top()+1);
                            break;
                        }else{
                            temp.pop();
                        }
                    }
                    if(temp.empty())
                        ans.push_back(-1);
                }
            }
        }
        return ans;
    }
};

複雜度分析

• 時間複雜度：$O(nlogn)$
• 空間複雜度：$O(n)$