網易首頁 > 網易號 > 正文申請入駐

2025-12-18：電網維護。用go語言，有 c 個電站，編號從 1 到 c。它們之間通過 n 條無向電纜相連，connect

2025-12-18 00:12:58　來源: moonfdd

北京舉報

分享至

2025-12-18：電網維護。用go語言，有 c 個電站，編號從 1 到 c。它們之間通過 n 條無向電纜相連，connections 數組中每個元素 [u, v] 表示電站 u 和 v 之間有連接。通過這些連接能夠互相到達的一組電站構成一個“電網”（連通分量）。

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

? [1, x]（請求維護）：要求對電站 x 進行維護檢查。若 x 當前在線，則由 x 自行完成；若 x 已離線，則在與 x 同一連通分量內選擇編號最小且目前在線的電站來完成檢查；如果該連通分量中沒有任何在線電站，則返回 -1。
? [2, x]（下線）：將電站 x 設為離線狀態（不可用）。

需要按 queries 中的順序處理操作，并將所有類型為 [1, x] 的查詢的返回結果匯總成一個數組輸出。注意：電纜連接關系在整個過程中不變，節點即便離線也仍屬于原來的連通分量，下線操作不會改變連通結構。

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} 都在線，并組成一個電網。

查詢 [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。

題目來自力扣3607。

步驟一：構建初始圖結構

首先根據輸入的電纜連接關系connections構建一個無向圖。使用鄰接表來存儲這個圖，其中graph[i]是一個切片，保存了所有與電站i直接相連的電站編號。同時，初始化一個vertices切片，用于記錄每個電站的詳細信息，包括其所屬的電網（連通分量）ID以及是否處于離線狀態。初始時，所有電站的powerGridId設為 -1（表示未分配），offline設為 false（表示在線）。

步驟二：識別連通分量并建立優先隊列

接下來，需要找出圖中所有的連通分量（即“電網”）。代碼采用深度優先搜索（DFS）的方式進行遍歷：

? 從第一個未分配電網ID的電站開始，進行DFS遍歷，訪問所有能到達的電站。
? 在遍歷一個連通分量的過程中，為其中每一個電站分配相同的電網ID。
?關鍵操作：為每個連通分量創建一個最小堆（優先隊列）。在DFS遍歷時，將當前訪問的電站編號插入到該連通分量對應的堆中。由于堆是最小堆，堆頂元素始終是該連通分量中編號最小的電站。這一步是為后續高效查找最小在線電站做準備。

?? 步驟三：處理查詢操作

然后，按順序處理查詢數組queries中的每一個操作：

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

? 動作很簡單：找到電站x，將其offline標志設置為true。
? 注意，電站x雖然離線了，但它仍然屬于原來的連通分量，圖的連接結構沒有改變。代碼中并沒有在此時從堆中刪除x，這是一種延遲刪除策略。

2.請求維護操作 (op == 1)：

? 首先檢查電站x的當前狀態。如果x在線，那么結果就是x本身。
? 如果x已離線，則需要從其所屬的連通分量對應的最小堆中找出編號最小的在線電站。
?延遲刪除的清理：由于下線操作沒有直接刪除堆中的元素，堆頂可能是一個已經離線的電站。因此，需要不斷檢查堆頂元素：
- ? 如果堆頂電站已離線，就將其從堆中彈出 (heap.Pop)。
- ? 重復這個過程，直到堆頂是一個在線電站，或者堆為空。
? 如果堆不為空，那么當前的堆頂元素就是該連通分量中編號最小的在線電站，將其作為結果。如果堆為空，說明這個連通分量里沒有在線電站了，返回 -1。

?? 復雜度分析

?總的時間復雜度：
- ?構建圖：O(c + n)，其中 c 是電站數量，n 是電纜數量。
- ?DFS遍歷：同樣是 O(c + n)，每個節點和邊只訪問一次。
- ?處理查詢：這是最復雜的部分。每個下線操作 (op==2) 是 O(1) 時間。每個維護請求操作 (op==1) 的時間成本則取決于需要彈出多少個已離線的堆頂元素。在最壞情況下，可能每次操作都需要 O(log c) 時間（堆操作）。然而，由于每個電站最多被彈出一次，所有查詢中彈出操作的總次數是 O(c) 次。因此，處理 q 個查詢的總時間復雜度可以近似為 O((c + q) log c)。
?總的額外空間復雜度：
- ? 圖結構graph需要 O(c + n) 的空間。
- ?vertices數組需要 O(c) 的空間。
- ? 各個連通分量的最小堆總共存儲了 c 個電站編號，所以也是 O(c) 的空間。
- ? 綜合來看，總的額外空間復雜度為 O(c + n)。

Go完整代碼如下：

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]:
    # 構建鄰接表
    graph = [[] for _ in range(c + 1)]
    # 頂點信息
    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)
    # 初始化電網列表
    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)
    # 遍歷所有頂點，找到所有連通分量
    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']]
                # 彈出所有離線的頂點
                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

 # 測試用例
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)  # 輸出結果

C++完整代碼如下：

  

  

  

  


 using namespace std;

 // 頂點結構體
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) { 
 
 
      
 // 構建鄰接表 
 
 
     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); 
 
 
     } 
 
 
 
 
      
 // 存儲所有電網（每個電網是一個最小堆） 
 
 
     vector 
 
 int 
 , vector< 
 int 
 >, greater< 
 int 
 >>> powerGrids; 
 
 
      
 int 
  powerGridId =  
 0 
 ; 
 
 
 
 
      
 // 遍歷所有頂點，找到連通分量 
 
 
      
 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 
  { 
 
 
                  
 // 獲取頂點所在的電網 
 
 
                 auto& powerGrid = powerGrids[vertices[x].powerGridId]; 
 
 
 
 
                  
 // 彈出所有離線的頂點 
 
 
                 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 
 ; 
 
 
 }

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

特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.