專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

之前我一直以為雙非院校的學(xué)生進大廠要難一些，92院校的想進大廠應(yīng)該會容易很多。今天在網(wǎng)上看了一個900多人的投票，除了52%的是觀望以外，211投票最高的是11.9%，也就是20%以下的人能夠進大廠，這個確實有點離譜，我覺得應(yīng)該不至于這么低，可能也和專業(yè)有關(guān)。985投票最高的是7.1%，80%以上都能進大廠，不過投票第二的是6.8%，20%以下能夠進大廠，這個確實有點懸殊。不過有一點可以肯定，學(xué)歷越高進大廠的機率就會越大。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第2368題：受限條件下可到達節(jié)點的數(shù)目。

問題描述

來源：LeetCode第2368題

難度：中等

現(xiàn)有一棵由 n 個節(jié)點組成的無向樹，節(jié)點編號從 0 到 n - 1 ，共有 n - 1 條邊。給你一個二維整數(shù)數(shù)組 edges ，長度為 n - 1 ，其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間存在一條邊。另給你一個整數(shù)數(shù)組 restricted 表示受限節(jié)點。

在不訪問受限節(jié)點的前提下，返回你可以從節(jié)點 0 到達的最多節(jié)點數(shù)目。注意，節(jié)點 0 不會標記為受限節(jié)點。

示例1：

輸入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] 輸出：4 解釋：上圖所示正是這棵樹。 在不訪問受限節(jié)點的前提下，只有節(jié)點 [0,1,2,3] 可以從節(jié)點 0 到達。

示例2：

輸入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1] 輸出：3 解釋：上圖所示正是這棵樹。 在不訪問受限節(jié)點的前提下，只有節(jié)點 [0,5,6] 可以從節(jié)點 0 到達。

• 2 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 0 <= ai, bi < n

• ai != bi

• edges 表示一棵有效的樹

• 1 <= restricted.length < n

• 1 <= restricted[i] < n

• restricted 中的所有值 互不相同

問題分析

這題說的是在一個有n個節(jié)點組成的無向樹中，節(jié)點0所能到達的節(jié)點個數(shù)。這里說的無向樹其實就是一個 無向圖 ，所以這題也就是對圖的遍歷，注意還要跳過受限的節(jié)點。對于圖的遍歷常見的BFS，DFS和并查集，實際上這題使用這三種方式中的任何一種都可以解決，我們來看一下使用DFS怎么解決的。

從節(jié)點0開始遞歸遍歷，查找所有和節(jié)點0相連的節(jié)點，為了方便查找我們可以使用 n 個集合記錄和每一個節(jié)點相連的所有節(jié)點，類似于圖的鄰接表，還要使用一個數(shù)組來記錄受限的節(jié)點和已經(jīng)被訪問過的節(jié)點，代碼如下。

JAVA：

public int reachableNodes(int n, int[][] edges, int[] restricted) {     // n個集合，記錄與每一個節(jié)點相連的所有節(jié)點     List
         
 [] lists =  new List[n];      for ( int i =  0; i < n; i++) // 初始化集合         lists[i] =  new ArrayList();      for ( int[] edge : edges) {          // 因為是無向圖，所以如果a和b相連，那么b也和a相連。         lists[edge[ 0]].add(edge[ 1]);         lists[edge[ 1]].add(edge[ 0]);     }      // 記錄受限的節(jié)點和已經(jīng)訪問過的節(jié)點      boolean[] isRestricted =  new  boolean[n];      for ( int restrict : restricted)         isRestricted[restrict] =  true;      return dfs( 0, lists, isRestricted); } private int dfs(int start, List [] lists,  boolean[] isRestricted)  {      if (isRestricted[start]) // 如果是受限的節(jié)點或者是已經(jīng)訪問過的節(jié)點，直接跳過          return  0;     isRestricted[start] =  true; // 標記為已訪問      int res =  1;      for ( int num : lists[start]) // 遞歸和當前節(jié)點相連的所有節(jié)點。         res += dfs(num, lists, isRestricted);      return res; }

C++：

public:     int reachableNodes(int n, vector

 > &edges, vector

  &restricted) {         vector

 > lists(n); // n個集合，記錄與每一個節(jié)點相連的所有節(jié)點         for (auto &edge: edges) {             // 因為是無向圖，所以如果a和b相連，那么b也和a相連。             lists[edge[0]].push_back(edge[1]);             lists[edge[1]].push_back(edge[0]);         }         // 記錄受限的節(jié)點和已經(jīng)訪問過的節(jié)點         vector

  isRestricted(n);         for (int restrict: restricted)             isRestricted[restrict] = true;         return dfs(0, lists, isRestricted);     }     int dfs(int start, vector

 > &lists, vector

  &isRestricted) {         if (isRestricted[start])// 如果是受限的節(jié)點或者是已經(jīng)訪問過的節(jié)點，直接跳過             return 0;         isRestricted[start] = true;// 標記為已訪問         int res = 1;         for (int num: lists[start])// 遞歸和當前節(jié)點相連的所有節(jié)點。             res += dfs(num, lists, isRestricted);         return res;     }

Python：

def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:     def dfs(start: int, lists: List[List[int]], isRestricted: List[bool]):         if isRestricted[start]:  # 如果是受限的節(jié)點或者是已經(jīng)訪問過的節(jié)點，直接跳過             return 0         isRestricted[start] = True  # 標記為已訪問         res = 1         for num in lists[start]:  # 遞歸和當前節(jié)點相連的所有節(jié)點。             res += dfs(num, lists, isRestricted)         return res     # n個集合，記錄與每一個節(jié)點相連的所有節(jié)點     lists = [[] for _ in range(n)]     # 因為是無向圖，所以如果a和b相連，那么b也和a相連。     for edge in edges:         lists[edge[0]].append(edge[1])         lists[edge[1]].append(edge[0])     # 記錄受限的節(jié)點和已經(jīng)訪問過的節(jié)點     isRestricted = [0] * n     for restrict in restricted:         isRestricted[restrict] = True     return dfs(0, lists, isRestricted)

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。