0684. Redundant Connection (Medium)

寫在前面

從 LeetCode 學演算法 + 面試成功指南**http://bit.ly/zeroclg

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

Question

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1

1
2

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2

1
2

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Constraints

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

分析/解題

在這個問題中，一棵樹是一個無向圖(undirected graph)，且當中沒有環(cycle)。給定一個圖，當中有n個node，標記為從1到n，其中有多一個邊(edge)；多出來的邊是由1到n選出兩個不同的節點(vertices, vertex的複數)所構成的，且並非已經存在的邊。這個圖是由一個長度為n的陣列edges來表示的，其每個元素edges[i]=[ai, bi]表示在圖中，ai和bi兩個節點中間有一個邊連結。

請回傳一個可以在移除後令這個圖可以形成一棵含有n個節點的樹的邊，如果有多個答案的話，請回傳讓其發生在最後的輸入。

好的，光翻譯題目就是一個很麻煩的事情，這也是為什麼從之前到現在始終不太想作圖(graph)相關的文章：因為實在太麻煩了，且不好解釋XD

那我們今天就來挑戰看看吧！希望在看完本篇文章以後，大家還醒著(笑)XD

在解這題之前，我們應該要先對圖作一點基本介紹：
圖(graph)是一種描述資料與資料之間的連結(不是人與人之間的)的結構，
當中最主要會分為兩個主要的元素：vertex(節點)及edge(邊/線段)。
節點可能擁有自己的一些屬性或值，這個可以依照定義而改變，而節點和節點之間，則是透過邊來連接，因此在同一張圖內，如果有超過一個節點，那它們至少要有能夠相連的邊連結彼此(不然就不會是同一張圖了！)。

接下來另一個很重要的點是，圖可以分為有向圖(directed graph) 和無向圖(undirected graph) ，什麼意思呢？

舉例來說，筆者對台北還不夠熟悉的時候，騎著機車在台北附近總是容易繞一大圈才走到自己的目的地，而且回程的時候還容易繞錯路，其中一個原因就是單行道 。單行道表示了今天從A走到B可能可以走XX路，但從B到A可能要走OO路接RR路才行，因為XX路是單向的；換句話說，當從A到B和從B到A無法等價看待的時候，我們會稱這樣的圖為有向圖，因為其關連性不能夠直接反過來也成立。這種圖在繪製上的體現就是節點到節點之間會有箭頭以表示方向 ，對於本題來說，由於給定是無方向的，所以讀者會看到圖形上的連接僅有線條，沒有箭頭。

接著是環(cycle) ，如果一個圖可以從某個節點出發，經過不重複 的節點(起點除外)，最終又能回到起始的節點，我們稱這個圖具有一個循環。

圖的表示方式一般有兩種：

1. Adjacency Matrix(相鄰矩陣)，也就是如果有N個節點，就開一個NxN的矩陣Mat，當中如果A點跟B點有edge的話，Mat[A][B]=1，否則為0；可以想見，如果某個圖是無向圖的話，這個矩陣應該會沿對角線相對稱(因為Mat[A][B]會和Mat[B][A]等價)。

2. Adjacency List(相鄰串列)，也就是對每個節點，都用一個串列來列出跟這個節點有相連的邊的所有節點。

一般而言，如果總體的edge數量較多的話會使用相鄰矩陣，比較少的話則會使用相鄰串列。

其它跟圖有關的基礎其實還很多，我們容後有機會再慢慢講。

回到我們的題目，其實它是一個相對簡單的圖，
因為要連接n個節點總體只需要n-1個邊，而這個圖有n個邊，
要讓這個圖不成環，只能將其中一個會構成環的邊給去除掉。

那麼，我們怎麼知道哪邊會有環成立呢？
這邊我們可以使用union find的概念來處理。
union find其實是在探究併查集( Disjoint-set data structure**)** 的問題。
用最白話的方式，就是「我們有沒有同一國」的概念。
什麼意思呢？

假設一個班級有幾個小團體，這些小團體跟幫派一樣很講17且不能重覆加入，我們現在想知道究竟哪些同學屬於哪個小團體，要怎麼找呢？
其實很簡單，就是把每個同學叫過來問：「你的老大是誰？」

舉例來說，如果有一個班級有兩個小團體，它們之間的層級分部是這樣的：

A
|
B C
| |
DE- F

G
|
H
|
I

D會告訴你他的老大是B；
E會告訴你他的老大是C；
然後B、C會告訴你他們的老大是A；
最後問到A他會說：「我就是老大！」
於是我們就會發現B、C、D、E這四位其實都是隸屬於A的，
也就是他們都是同一團體的。而G、H、I則屬於另一個團體。
因此，我們可以對某個節點找到它最上層的節點，
用這個節點來定義它所屬的團體，同時在過程中依照新增的邊來合併彼此的老大，這個過程叫作find 。

那麼，我們換個角度來思考：
依照上面的概念，每個節點之間的邊，其實就可以代表它們是同一國的，
那麼，如果在看到這個邊之前，它們就已經有相同的老大了呢？
比如上面的圖而言，對於E和F來說，由於有A-C-E跟A-C-F，
因此E跟F都知道自己的老大是A。
接著我們看到E-F的這條邊連結起來，就意味著這邊構成了一個環 ！
因為前面E已經可以連到A，F也可以連到A表示EAF之間可以連接起來，
因此E-F的連接就給這之間構成了一個環。

因此，我們可以利用這點，來找出構成環的邊，就是我們要的答案了！
因為節點和邊的總數量我們知道是n，所有節點也只有1~n，
所以我們可以使用一個陣列或串列來簡單表示某個節點的老大是哪個節點。
如果它自己就是最大的老大的話，那麼我們就用-1來代表它沒有更上層了。

因此，我們的解題步驟應該像這樣：

1. 產生一個root的陣列/串列，其長度為n+1 (比較方便對應1~n)，
   其初始值均為**-1** 。
2. 對於edges中的每個邊edge，使用find 函式找到它們的老大x跟y，
   檢查x和y是否相同；若相同，表示這個邊構成了一個環 ，回傳edge 即可；
   若不同，則須統一老大，將root[x]設定為y (將x這系列的上層往y這邊合併)。
3. 如果檢查完均檢查不到，則在外層回傳空的陣列/串列表示沒找到(但題目表示應該都會存在答案，所以理論上不會走到這邊)。

在find函式 的定義中，輸入應該是root這個陣列跟要被確認的節點i：

1. 使用迴圈，當root[i]不是-1時，令i = root[i] ，往上找尋更上層的老大。
2. 直到迴圈結束，這時候的i應該是最上層了，就回傳i 即可。

依此，寫成程式碼如下：

Java

Java的部份可以使用Arrays.fill來給定一整組的陣列初始值。

Python

Python的部分則直接用*號來初始化即可，同時使用子函式，
略去self相關的麻煩寫法。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(如果找尋root的時間沒有到最糟糕狀況的話為O(N)/O(N)，但我們在這個版本的只實作了find，最差狀況下find會一條線接上去，導致find的複雜度達到O(N)，這時候總體時間複雜度就會是O(N^2)。)

「如果要實作化簡的部份的話？」
(化簡的概念在於將中間尋找的部分也一併處理，也就是告訴沿路上的所有節點它們最大的老大是誰，要怎麼作才能讓整個路徑更短，可以參見https://en.wikipedia.org/wiki/Disjoint-set_data_structure，或者參考LeetCode的Solution也有提供，原則上是看兩個小團之間的節點數量來進行誰併到誰的決定。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve