跳转至

3607. 电网维护

题目描述

给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。

这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。

最初，所有 电站均处于在线（正常运行）状态。

另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ：

  • [1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一 电网 中 编号最小 的在线电站解决。如果该电网中 不存在 任何 在线 电站，则返回 -1。

  • [2, x]：电站 x 离线（即变为非运行状态）。

返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。

注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

 

示例 1：

输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

输出： [3,2,3]

解释：

  • 最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。
  • 查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。
  • 查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。
  • 查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。
  • 查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。
  • 查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。

示例 2：

输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

输出： [1,-1]

解释：

  • 没有连接，因此每个电站是一个独立的电网。
  • 查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。
  • 查询 [2,1]：电站 1 离线。
  • 查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。

 

提示：

  • 1 <= c <= 105
  • 0 <= n == connections.length <= min(105, c * (c - 1) / 2)
  • connections[i].length == 2
  • 1 <= ui, vi <= c
  • ui != vi
  • 1 <= queries.length <= 2 * 105
  • queries[i].length == 2
  • queries[i][0] 为 1 或 2。
  • 1 <= queries[i][1] <= c

解法

方法一：并查集 + 有序集合

我们可以使用并查集（Union-Find）来维护电站之间的连接关系，从而确定每个电站所属的电网。对于每个电网，我们使用有序集合（如 Python 中的 SortedList、Java 中的 TreeSet 或 C++ 中的 std::set）来存储该电网中所有在线的电站编号，以便能够高效地查询和删除电站。

具体步骤如下：

  1. 初始化并查集，处理所有连接关系，将连接的电站合并到同一个集合中。
  2. 为每个电网创建一个有序集合，初始时将所有电站编号加入对应电网的集合中。
  3. 遍历查询列表：
    • 对于查询 \([1, x]\)，首先找到电站 \(x\) 所属的电网根节点，然后检查该电网的有序集合：
      • 如果电站 \(x\) 在线（存在于集合中），则返回 \(x\)。
      • 否则，返回集合中的最小编号电站（如果集合非空），否则返回 -1。
    • 对于查询 \([2, x]\)，找到电站 \(x\) 所属的电网根节点，并将电站 \(x\) 从该电网的有序集合中删除，表示该电站离线。
  4. 最后，返回所有类型为 \([1, x]\) 的查询结果。

时间复杂度 \(O((c + n + q) \log c)\)，空间复杂度 \(O(c)\)。其中 \(c\) 是电站数量，而 \(n\) 和 \(q\) 分别是连接数量和查询数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def processQueries(
        self, c: int, connections: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        uf = UnionFind(c + 1)
        for u, v in connections:
            uf.union(u, v)
        st = [SortedList() for _ in range(c + 1)]
        for i in range(1, c + 1):
            st[uf.find(i)].add(i)
        ans = []
        for a, x in queries:
            root = uf.find(x)
            if a == 1:
                if x in st[root]:
                    ans.append(x)
                elif len(st[root]):
                    ans.append(st[root][0])
                else:
                    ans.append(-1)
            else:
                st[root].discard(x)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class UnionFind {
    private final int[] p;
    private final int[] size;

    public UnionFind(int n) {
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public boolean union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            return false;
        }
        if (size[pa] > size[pb]) {
            p[pb] = pa;
            size[pa] += size[pb];
        } else {
            p[pa] = pb;
            size[pb] += size[pa];
        }
        return true;
    }
}

class Solution {
    public int[] processQueries(int c, int[][] connections, int[][] queries) {
        UnionFind uf = new UnionFind(c + 1);
        for (int[] e : connections) {
            uf.union(e[0], e[1]);
        }

        TreeSet<Integer>[] st = new TreeSet[c + 1];
        Arrays.setAll(st, k -> new TreeSet<>());
        for (int i = 1; i <= c; i++) {
            int root = uf.find(i);
            st[root].add(i);
        }

        List<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            int a = q[0], x = q[1];
            int root = uf.find(x);

            if (a == 1) {
                if (st[root].contains(x)) {
                    ans.add(x);
                } else if (!st[root].isEmpty()) {
                    ans.add(st[root].first());
                } else {
                    ans.add(-1);
                }
            } else {
                st[root].remove(x);
            }
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class UnionFind {
public:
    UnionFind(int n) {
        p = vector<int>(n);
        size = vector<int>(n, 1);
        iota(p.begin(), p.end(), 0);
    }

    bool unite(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            return false;
        }
        if (size[pa] > size[pb]) {
            p[pb] = pa;
            size[pa] += size[pb];
        } else {
            p[pa] = pb;
            size[pb] += size[pa];
        }
        return true;
    }

    int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

private:
    vector<int> p, size;
};

class Solution {
public:
    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        UnionFind uf(c + 1);
        for (auto& e : connections) {
            uf.unite(e[0], e[1]);
        }

        vector<set<int>> st(c + 1);
        for (int i = 1; i <= c; i++) {
            st[uf.find(i)].insert(i);
        }

        vector<int> ans;
        for (auto& q : queries) {
            int a = q[0], x = q[1];
            int root = uf.find(x);
            if (a == 1) {
                if (st[root].count(x)) {
                    ans.push_back(x);
                } else if (!st[root].empty()) {
                    ans.push_back(*st[root].begin());
                } else {
                    ans.push_back(-1);
                }
            } else {
                st[root].erase(x);
            }
        }
        return ans;
    }
};

1

评论