Medium
题目描述
给你一个整数 c，代表有 c 个电力站，每个站点都有一个唯一的标识符 id，从 1 到 c（基于 1 的索引）。
这些电力站通过 n 条双向电缆相互连接，用二维数组 connections 表示，其中每个元素 connections[i] = [ui, vi] 表示电力站 ui 和 vi 之间的连接。直接或间接连接的电力站形成一个电网。
最初，所有电力站都是在线的（可运行的）。
你还会得到一个二维数组 queries，其中每个查询是以下两种类型之一：
[1, x]：请求对电力站 x 进行维护检查。如果电力站 x 在线，它自己解决检查。如果电力站 x 离线，则由与 x 在同一电网中 id 最小的运行中电力站解决检查。如果该电网中不存在运行中的电力站，返回 -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]
示例 2：
输入：c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]
输出：[1,-1]
约束条件：
- 1 <= c <= 10^5
- 0 <= n == connections.length <= min(10^5, c * (c - 1) / 2)
- connections[i].length == 2
- 1 <= ui, vi <= c
- ui != vi
- 1 <= queries.length <= 2 * 10^5
- queries[i].length == 2
- queries[i][0] 是 1 或 2
- 1 <= queries[i][1] <= c
解题思路
这道题的核心在于维护电网的连通性以及每个连通分量中在线电力站的信息。
解题思路：
构建图和连通分量识别：使用DFS或BFS遍历整个图，为每个电力站分配其所属的连通分量ID。
数据结构设计：
- 使用邻接表表示图的连接关系
- 为每个连通分量维护一个有序集合（C++中用set，Python中用TreeSet或排序列表），存储该分量中所有在线的电力站ID
- 维护每个电力站所属的连通分量ID
查询处理：
- 对于查询 [1, x]：如果站点x在线，直接返回x；否则返回其所属连通分量中最小的在线站点ID，如果没有则返回-1
- 对于查询 [2, x]：将站点x从其连通分量的在线集合中移除
优化关键：预计算所有连通分量，然后使用有序集合在O(log n)时间内处理每个查询。
这种方法避免了每次查询都重新搜索图的开销，通过预处理和高效的数据结构实现了最优的时间复杂度。
代码实现
class Solution {
public:
vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
// 构建邻接表
vector<vector<int>> graph(c + 1);
for (auto& conn : connections) {
graph[conn[0]].push_back(conn[1]);
graph[conn[1]].push_back(conn[0]);
}
// 使用DFS找到连通分量
vector<int> component(c + 1, -1);
int compCount = 0;
function<void(int, int)> dfs = [&](int node, int comp) {
component[node] = comp;
for (int neighbor : graph[node]) {
if (component[neighbor] == -1) {
dfs(neighbor, comp);
}
}
};
for (int i = 1; i <= c; i++) {
if (component[i] == -1) {
dfs(i, compCount++);
}
}
// 为每个连通分量维护在线站点的有序集合
vector<set<int>> onlineStations(compCount);
for (int i = 1; i <= c; i++) {
onlineStations[component[i]].insert(i);
}
vector<int> result;
for (auto& query : queries) {
if (query[0] == 1) {
int x = query[1];
int comp = component[x];
auto& stations = onlineStations[comp];
if (stations.count(x)) {
result.push_back(x);
} else if (!stations.empty()) {
result.push_back(*stations.begin());
} else {
result.push_back(-1);
}
} else {
int x = query[1];
int comp = component[x];
onlineStations[comp].erase(x);
}
}
return result;
}
};
class Solution:
def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
import bisect
# 构建邻接表
graph = defaultdict(list)
for u, v in connections:
graph[u].append(v)
graph[v].append(u)
# 使用DFS找到连通分量
component = [-1] * (c + 1)
comp_count = 0
def dfs(node, comp):
component[node] = comp
for neighbor in graph[node]:
if component[neighbor] == -1:
dfs(neighbor, comp)
for i in range(1, c + 1):
if component[i] == -1:
dfs(i, comp_count)
comp_count += 1
# 为每个连通分量维护在线站点的有序列表
online_stations = [[] for _ in range(comp_count)]
for i in range(1, c + 1):
online_stations[component[i]].append(i)
result = []
for query in queries:
if query[0] == 1:
x = query[1]
comp = component[x]
stations = online_stations[comp]
# 检查x是否在线
pos = bisect.bisect_left(stations, x)
if pos < len(stations) and stations[pos] == x:
result.append(x)
elif stations:
result.append(stations[0])
else:
result.append(-1)
else:
x = query[1]
comp = component[x]
stations = online_stations[comp]
pos = bisect.bisect_left(stations, x)
if pos < len(stations) and stations[pos] == x:
stations.pop(pos)
return result
public class Solution {
public int[] ProcessQueries(int c, int[][] connections, int[][] queries) {
// 构建邻接表
var graph = new List<int>[c + 1];
for (int i = 0; i <= c; i++) {
graph[i] = new List<int>();
}
foreach (var conn in connections) {
graph[conn[0]].Add(conn[1]);
graph[conn[1]].Add(conn[0]);
}
// 使用DFS找到连通分量
var component = new int[c + 1];
Array.Fill(component, -1);
int compCount = 0;
void Dfs(int node, int comp) {
component[node] = comp;
foreach (int neighbor in graph[node]) {
if (component[neighbor] == -1) {
Dfs(neighbor, comp);
}
}
}
for (int i = 1; i <= c; i++) {
if (component[i] == -1) {
Dfs(i, compCount++);
}
}
// 为每个连通分量维护在线站点的有序集合
var onlineStations = new SortedSet<int>[compCount];
for (int i = 0; i < compCount; i++) {
onlineStations[i] = new SortedSet<int>();
}
for (int i = 1; i <= c; i++) {
onlineStations[component[i]].Add(i);
}
var result = new List<int>();
foreach (var query in queries) {
if (query[0] == 1) {
int x = query[1];
int comp = component[x];
var stations = onlineStations[comp];
if (stations.Contains(x)) {
result.Add(x);
} else if (stations.Count > 0) {
result.Add(stations.Min);
} else {
result.Add(-1);
}
} else {
int x = query[1];
int comp = component[x];
onlineStations[comp].Remove(x);
}
}
return result.ToArray();
}
}
var processQueries = function(c, connections, queries) {
// Build adjacency list
const graph = Array.from({length: c + 1}, () => []);
for (const [u, v] of connections) {
graph[u].push(v);
graph[v].push(u);
}
// Track online status
const online = Array(c + 1).fill(true);
online[0] = false; // 0-index is not used
const result = [];
// BFS to find connected component
function findMinOnlineInComponent(start) {
const visited = Array(c + 1).fill(false);
const queue = [start];
visited[start] = true;
let minOnline = Infinity;
while (queue.length > 0) {
const node = queue.shift();
if (online[node]) {
minOnline = Math.min(minOnline, node);
}
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
return minOnline === Infinity ? -1 : minOnline;
}
for (const [type, x] of queries) {
if (type === 1) {
if (online[x]) {
result.push(x);
} else {
result.push(findMinOnlineInComponent(x));
}
} else {
online[x] = false;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(c + n + q log c) | DFS遍历O(c+n)，q次查询每次O(log c) |
| 空间复杂度 | O(c + n) | 存储图的邻接表和连通分量信息 |