2025-12-18：電網(wǎng)維護(hù)。用go語(yǔ)言，有 c 個(gè)電站，編號(hào)從 1 到 c。它們之間通過 n 條無(wú)向電纜相連，connections 數(shù)組中每個(gè)元素 [u, v] 表示電站 u 和 v 之間有連接。通過這些連接能夠互相到達(dá)的一組電站構(gòu)成一個(gè)“電網(wǎng)”（連通分量）。

起初所有電站都是在線（正常工作）的。隨后會(huì)有一系列操作，記錄在 queries 數(shù)組中，每條操作有兩種形式：

• ? [1, x]（請(qǐng)求維護(hù)）：要求對(duì)電站 x 進(jìn)行維護(hù)檢查。若 x 當(dāng)前在線，則由 x 自行完成；若 x 已離線，則在與 x 同一連通分量?jī)?nèi)選擇編號(hào)最小且目前在線的電站來(lái)完成檢查；如果該連通分量中沒有任何在線電站，則返回 -1。

• ? [2, x]（下線）：將電站 x 設(shè)為離線狀態(tài)（不可用）。

需要按 queries 中的順序處理操作，并將所有類型為 [1, x] 的查詢的返回結(jié)果匯總成一個(gè)數(shù)組輸出。注意：電纜連接關(guān)系在整個(gè)過程中不變，節(jié)點(diǎn)即便離線也仍屬于原來(lái)的連通分量，下線操作不會(huì)改變連通結(jié)構(gòu)。

1 <= c <= 100000。

0 <= n == connections.length <= min(100000, c * (c - 1) / 2)。

connections[i].length == 2。

1 <= ui, vi <= c。

ui != vi。

1 <= queries.length <= 2 * 100000。

queries[i].length == 2。

queries[i][0] 為 1 或 2。

1 <= queries[i][1] <= c。

輸入： 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} 都在線，并組成一個(gè)電網(wǎng)。

查詢 [1,3]：電站 3 在線，因此維護(hù)檢查由電站 3 自行解決。

查詢 [2,1]：電站 1 離線。剩余在線電站為 {2, 3, 4, 5}。

查詢 [1,1]：電站 1 離線，因此檢查由電網(wǎng)中編號(hào)最小的在線電站解決，即電站 2。

查詢 [2,2]：電站 2 離線。剩余在線電站為 {3, 4, 5}。

查詢 [1,2]：電站 2 離線，因此檢查由電網(wǎng)中編號(hào)最小的在線電站解決，即電站 3。

題目來(lái)自力扣3607。

步驟一：構(gòu)建初始圖結(jié)構(gòu)

首先根據(jù)輸入的電纜連接關(guān)系connections構(gòu)建一個(gè)無(wú)向圖。使用鄰接表來(lái)存儲(chǔ)這個(gè)圖，其中graph[i]是一個(gè)切片，保存了所有與電站i直接相連的電站編號(hào)。同時(shí)，初始化一個(gè)vertices切片，用于記錄每個(gè)電站的詳細(xì)信息，包括其所屬的電網(wǎng)（連通分量）ID以及是否處于離線狀態(tài)。初始時(shí)，所有電站的powerGridId設(shè)為 -1（表示未分配），offline設(shè)為 false（表示在線）。

步驟二：識(shí)別連通分量并建立優(yōu)先隊(duì)列

接下來(lái)，需要找出圖中所有的連通分量（即“電網(wǎng)”）。代碼采用深度優(yōu)先搜索（DFS）的方式進(jìn)行遍歷：

• ? 從第一個(gè)未分配電網(wǎng)ID的電站開始，進(jìn)行DFS遍歷，訪問所有能到達(dá)的電站。

• ? 在遍歷一個(gè)連通分量的過程中，為其中每一個(gè)電站分配相同的電網(wǎng)ID。

• ?關(guān)鍵操作：為每個(gè)連通分量創(chuàng)建一個(gè)最小堆（優(yōu)先隊(duì)列）。在DFS遍歷時(shí)，將當(dāng)前訪問的電站編號(hào)插入到該連通分量對(duì)應(yīng)的堆中。由于堆是最小堆，堆頂元素始終是該連通分量中編號(hào)最小的電站。這一步是為后續(xù)高效查找最小在線電站做準(zhǔn)備。

然后，按順序處理查詢數(shù)組queries中的每一個(gè)操作：

1. 1.下線操作 (op == 2)：

• ? 動(dòng)作很簡(jiǎn)單：找到電站x，將其offline標(biāo)志設(shè)置為true。

• ? 注意，電站x雖然離線了，但它仍然屬于原來(lái)的連通分量，圖的連接結(jié)構(gòu)沒有改變。代碼中并沒有在此時(shí)從堆中刪除x，這是一種延遲刪除策略。

2.請(qǐng)求維護(hù)操作 (op == 1)：

• ? 首先檢查電站x的當(dāng)前狀態(tài)。如果x在線，那么結(jié)果就是x本身。

• ? 如果x已離線，則需要從其所屬的連通分量對(duì)應(yīng)的最小堆中找出編號(hào)最小的在線電站。

• ?延遲刪除的清理：由于下線操作沒有直接刪除堆中的元素，堆頂可能是一個(gè)已經(jīng)離線的電站。因此，需要不斷檢查堆頂元素：

• • ? 如果堆頂電站已離線，就將其從堆中彈出 (heap.Pop)。

  • ? 重復(fù)這個(gè)過程，直到堆頂是一個(gè)在線電站，或者堆為空。

• ? 如果堆不為空，那么當(dāng)前的堆頂元素就是該連通分量中編號(hào)最小的在線電站，將其作為結(jié)果。如果堆為空，說明這個(gè)連通分量里沒有在線電站了，返回 -1。

• ?總的時(shí)間復(fù)雜度：

• • ?構(gòu)建圖：O(c + n)，其中 c 是電站數(shù)量，n 是電纜數(shù)量。

  • ?DFS遍歷：同樣是 O(c + n)，每個(gè)節(jié)點(diǎn)和邊只訪問一次。

  • ?處理查詢：這是最復(fù)雜的部分。每個(gè)下線操作 (op==2) 是 O(1) 時(shí)間。每個(gè)維護(hù)請(qǐng)求操作 (op==1) 的時(shí)間成本則取決于需要彈出多少個(gè)已離線的堆頂元素。在最壞情況下，可能每次操作都需要 O(log c) 時(shí)間（堆操作）。然而，由于每個(gè)電站最多被彈出一次，所有查詢中彈出操作的總次數(shù)是 O(c) 次。因此，處理 q 個(gè)查詢的總時(shí)間復(fù)雜度可以近似為 O((c + q) log c)。

• ?總的額外空間復(fù)雜度：

• • ? 圖結(jié)構(gòu)graph需要 O(c + n) 的空間。

  • ?vertices數(shù)組需要 O(c) 的空間。

  • ? 各個(gè)連通分量的最小堆總共存儲(chǔ)了 c 個(gè)電站編號(hào)，所以也是 O(c) 的空間。

  • ? 綜合來(lái)看，總的額外空間復(fù)雜度為 O(c + n)。

package main

 import (
    "container/heap"
    "fmt"
)

 func processQueries(c int, connections [][]int, queries [][]int) []int {
    graph := make([][]int, c+1)
    vertices := make([]Vertex, c+1)

     for i := 0; i <= c; i++ {
        graph[i] = make([]int, 0)
        vertices[i] = Vertex{vertexId: i, powerGridId: -1}
    }

     for _, conn := range connections {
        u, v := conn[0], conn[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    powerGrids := make([]*IntHeap, 0)
    for i, powerGridId := 1, 0; i <= c; i++ {
        v := &vertices[i]
        if v.powerGridId == -1 {
            powerGrid := &IntHeap{}
            heap.Init(powerGrid)
            traverse(v, powerGridId, powerGrid, graph, vertices)
            powerGrids = append(powerGrids, powerGrid)
            powerGridId++
        }
    }

     ans := make([]int, 0)
    for _, q := range queries {
        op, x := q[0], q[1]
        if op == 1 {
            if !vertices[x].offline {
                ans = append(ans, x)
            } else {
                powerGrid := powerGrids[vertices[x].powerGridId]
                for powerGrid.Len() > 0 && vertices[(*powerGrid)[0]].offline {
                    heap.Pop(powerGrid)
                }
                if powerGrid.Len() > 0 {
                    ans = append(ans, (*powerGrid)[0])
                } else {
                    ans = append(ans, -1)
                }
            }
        } elseif op == 2 {
            vertices[x].offline = true
        }
    }

     return ans
}

 func traverse(u *Vertex, powerGridId int, powerGrid *IntHeap, graph [][]int, vertices []Vertex) {
    u.powerGridId = powerGridId
    heap.Push(powerGrid, u.vertexId)
    for _, vid := range graph[u.vertexId] {
        v := &vertices[vid]
        if v.powerGridId == -1 {
            traverse(v, powerGridId, powerGrid, graph, vertices)
        }
    }
}

 type Vertex struct {
    vertexId    int
    offline     bool
    powerGridId int
}

 type IntHeap []int

 func (h IntHeap) Len() int           { returnlen(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

 func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

 func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

 func main() {
    c := 5
    connections := [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 5}}
    queries := [][]int{{1, 3}, {2, 1}, {1, 1}, {2, 2}, {1, 2}}
    result := processQueries(c, connections, queries)
    fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

 import heapq
from typing import List

 def processQueries(c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
    # 構(gòu)建鄰接表
    graph = [[] for _ in range(c + 1)]
    # 頂點(diǎn)信息
    vertices = [{'vertex_id': i, 'offline': False, 'power_grid_id': -1} for i in range(c + 1)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    # 初始化電網(wǎng)列表
    power_grids = []
    power_grid_id = 0
    # DFS遍歷連通分量
    def dfs(u: int, pg_id: int, pg_heap: List[int]):
        vertices[u]['power_grid_id'] = pg_id
        heapq.heappush(pg_heap, u)
        for v in graph[u]:
            if vertices[v]['power_grid_id'] == -1:
                dfs(v, pg_id, pg_heap)
    # 遍歷所有頂點(diǎn)，找到所有連通分量
    for i in range(1, c + 1):
        if vertices[i]['power_grid_id'] == -1:
            power_grid = []
            dfs(i, power_grid_id, power_grid)
            power_grids.append(power_grid)
            power_grid_id += 1
    ans = []
    for op, x in queries:
        if op == 1:  # 查詢操作
            if not vertices[x]['offline']:
                ans.append(x)
            else:
                pg = power_grids[vertices[x]['power_grid_id']]
                # 彈出所有離線的頂點(diǎn)
                while pg and vertices[pg[0]]['offline']:
                    heapq.heappop(pg)
                if pg:
                    ans.append(pg[0])
                else:
                    ans.append(-1)
        elif op == 2:  # 離線操作
            vertices[x]['offline'] = True
    return ans

 # 測(cè)試用例
if __name__ == "__main__":
    c = 5
    connections = [[1, 2], [2, 3], [3, 4], [4, 5]]
    queries = [[1, 3], [2, 1], [1, 1], [2, 2], [1, 2]]
    result = processQueries(c, connections, queries)
    print(result)  # 輸出結(jié)果

C++完整代碼如下：

  

  

  

  


 using namespace std;

 // 頂點(diǎn)結(jié)構(gòu)體
struct Vertex {
    int vertexId;
    bool offline;
    int powerGridId;

     Vertex(int id = 0) : vertexId(id), offline(false), powerGridId(-1) {}
};

 void traverse(Vertex* u, int powerGridId, priority_queue, greater>& powerGrid,
              vector 
 
 int 
 >>& graph, vector 
 
 & vertices) { 
 
 
 
     u->powerGridId = powerGridId; 
 
 
     powerGrid.push(u->vertexId); 
 
 
 
 
      
 for 
  ( 
 int 
  vid : graph[u->vertexId]) { 
 
 
         Vertex& v = vertices[vid]; 
 
 
          
 if 
  (v.powerGridId ==  
 -1 
 ) { 
 
 
             traverse(&v, powerGridId, powerGrid, graph, vertices); 
 
 
         } 
 
 
     } 
 
 
 } 
 
 
 
 
 vector< 
 int 
 > processQueries( 
 int 
  c, vector 
 
 int 
 >>& connections, vector 
 
 int 
 >>& queries) { 
 
 
      
 // 構(gòu)建鄰接表 
 
 
     vector 
 
 int 
 >> graph(c +  
 1 
 ); 
 
 
     vector 
 
 vertices(c +  
 
 1 
 ); 
 
 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i <= c; i++) { 
 
 
         vertices[i] = Vertex(i); 
 
 
     } 
 
 
 
 
      
 for 
  (auto& conn : connections) { 
 
 
          
 int 
  u = conn[ 
 0 
 ], v = conn[ 
 1 
 ]; 
 
 
         graph[u].push_back(v); 
 
 
         graph[v].push_back(u); 
 
 
     } 
 
 
 
 
      
 // 存儲(chǔ)所有電網(wǎng)（每個(gè)電網(wǎng)是一個(gè)最小堆） 
 
 
     vector 
 
 int 
 , vector< 
 int 
 >, greater< 
 int 
 >>> powerGrids; 
 
 
      
 int 
  powerGridId =  
 0 
 ; 
 
 
 
 
      
 // 遍歷所有頂點(diǎn)，找到連通分量 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i <= c; i++) { 
 
 
         Vertex& v = vertices[i]; 
 
 
          
 if 
  (v.powerGridId ==  
 -1 
 ) { 
 
 
             priority_queue< 
 int 
 , vector< 
 int 
 >, greater< 
 int 
 >> powerGrid; 
 
 
             traverse(&v, powerGridId, powerGrid, graph, vertices); 
 
 
             powerGrids.push_back(powerGrid); 
 
 
             powerGridId++; 
 
 
         } 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > ans; 
 
 
 
 
      
 for 
  (auto& q : queries) { 
 
 
          
 int 
  op = q[ 
 0 
 ], x = q[ 
 1 
 ]; 
 
 
 
 
          
 if 
  (op ==  
 1 
 ) {   
 // 查詢操作 
 
 
              
 if 
  (!vertices[x].offline) { 
 
 
                 ans.push_back(x); 
 
 
             }  
 else 
  { 
 
 
                  
 // 獲取頂點(diǎn)所在的電網(wǎng) 
 
 
                 auto& powerGrid = powerGrids[vertices[x].powerGridId]; 
 
 
 
 
                  
 // 彈出所有離線的頂點(diǎn) 
 
 
                 while (!powerGrid.empty() && vertices[powerGrid.top()].offline) { 
 
 
                     powerGrid.pop(); 
 
 
                 } 
 
 
 
 
                  
 if 
  (!powerGrid.empty()) { 
 
 
                     ans.push_back(powerGrid.top()); 
 
 
                 }  
 else 
  { 
 
 
                     ans.push_back( 
 -1 
 ); 
 
 
                 } 
 
 
             } 
 
 
         }  
 else 
 if 
  (op ==  
 2 
 ) {   
 // 離線操作 
 
 
             vertices[x].offline =  
 true 
 ; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  c =  
 5 
 ; 
 
 
     vector 
 
 int 
 >> connections = {{ 
 1 
 ,  
 2 
 }, { 
 2 
 ,  
 3 
 }, { 
 3 
 ,  
 4 
 }, { 
 4 
 ,  
 5 
 }}; 
 
 
     vector 
 
 int 
 >> queries = {{ 
 1 
 ,  
 3 
 }, { 
 2 
 ,  
 1 
 }, { 
 1 
 ,  
 1 
 }, { 
 2 
 ,  
 2 
 }, { 
 1 
 ,  
 2 
 }}; 
 
 
 
 
     vector< 
 int 
 > result = processQueries(c, connections, queries); 
 
 
 
 
     cout <<  
 "[" 
 ; 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); i++) { 
 
 
         cout << result[i]; 
 
 
          
 if 
  (i < result.size() -  
 1 
 ) { 
 
 
             cout <<  
 ", " 
 ; 
 
 
         } 
 
 
     } 
 
 
     cout <<  
 "]" 
  << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 
 
 
 

我們相信人工智能為普通人提供了一種“增強(qiáng)工具”，并致力于分享全方位的AI知識(shí)。在這里，您可以找到最新的AI科普文章、工具評(píng)測(cè)、提升效率的秘籍以及行業(yè)洞察。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來(lái)發(fā)展。