九章演算法 | Google 面試題：多餘的連接

04-24

作者丨戴助教+本助教

專欄丨九章演算法

1. 題目描述

a. 給定一個無向圖，這個圖是在一棵樹的基礎上加上一條邊構成的。問哪條邊可以刪掉使圖重新變成一棵樹？如果有多個答案那麼輸出輸入的邊中最後出現的那條。

b. 輸入輸出

Input: [[1,2], [1,3], [2,3]]Output: [2,3]Explanation: The given undirected graph will be like this: 1/ 2 - 3

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4]Explanation: The given undirected graph will be like this:5 - 1 - 2 | | 4 - 3

c. 注意給的邊有順序，當兩個點已經有共同的根結點時候，這條邊應該被刪除

d. 輸入保證[u,v] u<v,要求輸出也保證u<v

2.解題思路分析

Ⅰ. 首先思考使用暴力方式解決問題，我們窮舉那條需要刪除的邊，然後都過深度優先搜索（dfs）驗證刪完之後的圖是否為一棵樹，時間複雜度是O(n^2)，雖然已經不錯了，但這不是面試官預期的時間複雜度

Ⅱ. 我們換個思路考慮，遍歷所有邊，一邊遍歷一邊將當前邊加入到圖中。如果我們發現，有一條邊[u,v]還未曾加入到圖中時，u和v就已經通過其他若干邊相連，那麼這就是我們要找的「多餘」的邊。

Ⅲ. 如果我們還是用dfs去判斷u和v的連通性，那麼是O(n)的時間複雜度，總的時間複雜度仍是O(n^2)。這裡我們就要用到一種數據結構叫做並查集，可以在常數時間內兩個元素是否在同一集合（查詢操作）和把兩個元素合併到同一個集合（合併操作）。在並查集中，每個集合都有一個代表元素，我們稱之為祖先。

Ⅳ. 並查集的初始化：在最初的時候，根節點都是自己，我們用一個數組parent[i]=i來表示這個關係。

Ⅴ. 並查集的查詢操作：每次給邊的時候判斷兩個點的祖先節點，我們不停地通過調用parent函數向上尋找直到parent[i]==i

Ⅵ. 給出一條邊，兩個節點設置為l ,r 如果祖先節點father_l, father_r 不相同，說明此時l和r不向連，這條邊信息有用（不是一條多餘的邊），我們就通過並查集的合併操作將他們連在一起。具體操作需要將祖先節點接在一起，令parent[father_r]=father_l。

Ⅶ. 路徑壓縮優化：在做查詢操作的時候我們將parent[now] = find_father(parent[now])，是為了壓縮路徑，因為一旦兩棵樹合併，其中一些節點不是直接指向根節點的，不合併每次搜索會浪費大量時間

Ⅷ. 我們認為總的時間複雜度是O(n)，其中使用了路徑壓縮的並查集的常數非常小可以忽略

Ⅸ. 雖然題目強調如果有多個答案輸出最後一條，但用上述方法只會找到一條「多餘」的邊，所以代碼中是從前往後遍歷所有邊

3.參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

4.面試官角度分析

本題是一道中等偏簡單難度的題目，難點在於用到了比較高級的數據結構：並查集，且需要把並查集應用在具體題目，來幫助我們快速的判斷圖中的連通性。

5.lintcode相關問題

a. LintCode

b. LintCode

c. Number of Islands