题目地址：

https://leetcode.com/problems/power-grid-maintenance/description/

给定一个$n$阶无向无权图，顶点编号从$1$开始，每个点代表一个能量站，初始的时候每个能量站都是开启的。有若干操作，类型$1$的操作是询问$x$所在的连通块里，如果$x$未开启，则返回该连通块里开启的编号最小的能量站的编号，不存在就返回$-1$；如果$x$开启则返回$x$；类型$2$的操作是将$x$关闭。

可以用并查集和哈希表套平衡树做。并查集维护能量站的连通关系，平衡树维护每个连通块里的编号顺序的信息。对于询问$1$，先通过并查集找到$x$的祖宗，维护哈希表的value为key所在的连通块里开启的能量站的编号，这样就能找到满足条件的询问结果；询问$2$只需要执行在平衡树里删除操作即可。代码如下：

class Solution {
public:
  vector<int> processQueries(int c, vector<vector<int>> &es,
                             vector<vector<int>> &qs) {
    vector<int> p(c + 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](this auto &&find, int x) -> int {
      return x == p[x] ? x : p[x] = find(p[x]);
    };

    for (auto &e : es) {
      int pa = find(e[0]), pb = find(e[1]);
      if (pa != pb) p[pa] = pb;
    }

    unordered_map<int, set<int>> online;
    for (int i = 1; i <= c; i++)
      online[find(i)].insert(i);

    vector<int> res;
    for (auto &q : qs) {
      int type = q[0], x = q[1];
      auto &st = online[find(x)];
      if (type == 1) {
        if (st.empty()) res.push_back(-1);
        else if (st.count(x)) res.push_back(x);
        else res.push_back(*st.begin());
      } else st.erase(x);
    }
    return res;
  }
};

建图时间复杂度$O(m{\log }^{\ast }n)$，预处理时间$O(n\log n)$，类型$1$和$2$的查询时间都是$O(\log n)$，空间$O(n)$。