專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

一同學在網上發文稱，大三找到實習，學校不放，走不了，怎么辦？結果在評論區發現還不止他一個人遇到這種情況。我記得學校不是挺看重就業率的嗎，記得當年我畢業的時候，學校要求必須要簽三方協議之后才能拿畢業證。現在學生找到工作又不讓去實習，不知道學校咋想的？

不過我個人覺得這事不要和學校說，直接走就是了，如果學校要求必須回來到時候再回來，因為有些事不能問，一問就是不行，但你如果真做了實際上也沒事。這就好比參加學校運動會一樣，如果直接問輔導員我不參加行嗎？那肯定是不行的，但你如果真的不去實際上也沒事。

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

來看下今天的算法題，這題是LintCode的第3890題：無向圖中到環的距離。

問題描述

來源：LintCode第3890題

難度：困難

給定一個正整數 n，表示一個連通無向圖中的節點數，節點編號為 0 到 n - 1，該圖只包含一個環。

再給定一個二維整數數組 edges，其中 edges[i] = [node1, node2] 表示第 i 條邊是一條雙向連接了兩個節點 node1 和 node2 的邊。

兩個節點 a 和 b 的距離定義為 節點 a 到節點 b 所需要的最少邊數，返回一個長度為 n 的整數數組 res，求出圖中所有節點到這個環的距離，即 res[i] 表示節點 i 到環中節點所需要的最少邊數。

示例1：

輸入： n = 7 edges = [[1, 2], [2, 4], [4, 3], [3, 1], [0, 1], [5, 2], [6, 5]] 輸出： [1, 0, 0, 0, 0, 1, 2] 解釋： 如下圖 節點 1 - 4 構成了一個環，節點已經在環內，因此距離為 0 節點 0 到環的最小距離為 1 節點 5 到環的最小距離為 1 節點 6 到環的最小距離為 2

示例2：

輸入： n = 6 egdes = [[0, 1], [1, 2], [0, 2], [0, 3], [3, 4], [3, 5]] 輸出： [0, 0, 0, 1, 2, 2] 解釋： 如下圖 節點 0 - 2 構成了一個環，距離為 0 節點 3 到環的最小距離為 1 節點 4 到環的最小距離為 2 節點 5 到環的最小距離為 2

• 3≤n≤10^5

• 圖是連通的

• 圖僅有一個環

• 任何節點之間最多只有一條邊

問題分析

這題說的是給定一個無向圖，圖中有且只有一個環，計算所有頂點到環的最短距離。 這題我們可以使用 ，拓撲排序需要是無環圖，而這里是有環的，實際上沒有影響。

我們首先按照拓撲排序的思路把所有 度為 1 的頂點全部添加到隊列中 ，然后遍歷隊列中的頂點，當隊列中的頂點 i 出隊之后，和 i 相連的頂點 j 要把頂點 i 給移除，如果移除之后，頂點 j 的度也為 1 ，就把頂點 j 也添加到隊列中 。

因為在 環中的所有頂點至少有兩個度 ，所以除了環中的頂點，其它所有頂點都會入隊和出隊，這里我們還需要使用一個棧來記錄出隊的順序，也就是 每個頂點的上游頂點 。比如示例 1 中 5 是 6 的上游頂點，最后計算距離的時候先計算頂點 5 在計算頂點 6 。

最后入棧的頂點肯定是和環挨著的，所以我們需要先計算和環挨著的頂點，然后一步步往外擴散，類似與從環開始進行BFS計算。

JAVA：

public int[] distanceToCycle(int n, int[][] edges) {
    // 把二維數組轉成鄰接表
    Set
       
       
 [] g =  new Set[n];     Arrays.setAll(g, k ->  new HashSet<>());      for ( int e[] : edges) {         g[e[ 0]].add(e[ 1]);         g[e[ 1]].add(e[ 0]);     }     Queue  q =  new ArrayDeque<>();      for ( int i =  0; i < n; i++) {          if (g[i].size() ==  1) // 把度為 1 的頂點添加到隊列中             q.offer(i);     }      int[] parent =  new  int[n]; // 記錄拓撲排序中的上游頂點     Stack  stk =  new Stack<>();      while (!q.isEmpty()) {          int i = q.poll();         stk.push(i); // 頂點 i 壓棧。          for ( int j : g[i]) {             g[j].remove(i);             parent[i] = j; // 記錄 i 的上游頂點是 j              // 移除 i 之后，如果頂點 j 的度為 1 ，把頂點 j 添加到隊列中。              if (g[j].size() ==  1)                 q.offer(j);         }     }      int[] res =  new  int[n];      while (!stk.isEmpty()) {          int i = stk.pop(); // 先出棧的是和環挨著的，最后出棧的是離環最遠的。         res[i] = res[parent[i]] +  1;     }      return res; }

筆者簡介

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