Leetcode之并查集專題-684. 冗余連接（Redundant Connection）

?

在本問題中, 樹指的是一個連通且無環(huán)的無向圖。

輸入一個圖，該圖由一個有著N個節(jié)點 (節(jié)點值不重復1, 2, ..., N) 的樹及一條附加的邊構成。附加的邊的兩個頂點包含在1到N中間，這條附加的邊不屬于樹中已存在的邊。

結果圖是一個以邊組成的二維數組。每一個邊的元素是一對[u, v]?，滿足?u < v，表示連接頂點u?和v的無向圖的邊。

返回一條可以刪去的邊，使得結果圖是一個有著N個節(jié)點的樹。如果有多個答案，則返回二維數組中最后出現的邊。答案邊?[u, v]?應滿足相同的格式?u < v。

示例 1：

輸入: [[1,2], [1,3], [2,3]]
輸出: [2,3]
解釋: 給定的無向圖為:
  1
 / 2 - 3

示例 2：

輸入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
解釋: 給定的無向圖為:
5 - 1 - 2
    |   |
    4 - 3

注意:

• 輸入的二維數組大小在 3 到 1000。
• 二維數組中的整數在1到N之間，其中N是輸入數組的大小。

?

并查集問題中的最基本的問題，本題中為了不讓這個樹成環(huán)，需要找出最后一條讓它成環(huán)的路徑。

?

本題是并查集問題的第一題，介紹一下并查集和它的方法。

定義

并查集是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。

?

舉個簡單的例子來講：

現在有幾個大家族，每個家族有很多個分支，有N個人，分別為1-N，每個人都有自己的祖先。

現在我想知道 A?和 B是否是一個祖先？

1、首先，每個人都有自己的祖先，所以我們用一個數組來存儲A的祖先father[A]

2、每個人一開始，自己是自己的祖先。

3、根據輸入的數據，對其祖先進行更新或修改。

4、如果需要判斷A和B的祖先是否相同，比較father[A]和father[B]的值就可以了。

本題中，我們也可以把這個樹的問題，當作是祖先問題。

以示例1為例：

一開始，每個人的祖先是自己，即

father[1] = 1;　　father[2] = 2;　　father[3] = 3;

第一個數據[1,2]輸入：

father[2] = 1;

第二個數據[1,3]輸入：

father[3] = 1;

第三個數據[2,3]輸入，我們發(fā)現2和3的祖先已經不是自己了，即已經指派過祖先給它們了。

所以我們分別求一下2和3的祖先。

father[2] = 1;

father[3] = 1；

發(fā)現2和3屬于同一個祖先，所以2-3之間這條線不能連接，不然就成環(huán)了。

?

那么，如果2和3的祖先不想等的話呢？

舉個例子，2的祖先是4，3的祖先是5，那么我們可以讓4的祖先等于5來把它們加入到同一個家族里。

?

這題還可以路徑壓縮優(yōu)化一下：

class Solution {
    int[] family ;
    public int[] findRedundantConnection(int[][] edges) {
        family = new int[edges.length 1];
        for (int i = 0; i < edges.length 1; i  ) {
            family[i] = i;
        }
        for (int i = 0; i < edges.length; i  ) {
            int[] temp = edges[i];
            int first = temp[0];
            int second = temp[1];
            int father1 = getFather(first);
            int father2 = getFather(second);
            if(father1==father2){
                return temp;
            }else{
                family[father1] = father2;
            }
        }
        return new int[2];
    }
    public int getFather(int i){
        int father = family[i];
        if(father==i){
            return father;
        }else{
            return getFather(father);
        }

    }

}

?