🔗 🟡 684. Redundant Connection

tags: 圖(Graph), DFS, BFS, 併查集(Disjoint Set)

題意

在本題中，樹被認為是一個無向圖，它是連通的並且沒有循環。

給定一個圖，該圖起初是一棵有 nn 個節點的樹，節點標號從 11 到 nn，並且添加了一條額外的邊。添加的邊有兩個從 11 到 nn 中選擇的不同頂點，並且不是已經存在的邊。該圖以長度為 nn 的陣列 edgesedges 表示，其中 edges[i]=[ai,bi]edges[i] = [a_i, b_i] 表示在圖中的節點 aia_i 和 bib_i 之間存在一條邊。

返回一條可以刪除的邊，使得結果圖是一棵有 nn 個節點的樹。如果有多個答案，則返回輸入中最後出現的邊。

思路：併查集(Disjoint Set)

根據題意，題目給定的圖最後會形成一個有且僅有一個環的圖，而我們只需要刪除環上的任意一條邊，即可將其恢復成一棵樹。

而題目要求我們返回最後出現的那條邊，換句話說，我們可以依序添加邊，當遇到某條邊使得圖形成環時，該邊就是我們要找的邊。因此我們可以使用 併查集(Disjoint Set) 來追蹤圖中的連通性，並且在發現形成環的邊時，可以及時返回該邊。

併查集的基本原理是將每個節點初始化為一個獨立的集合，然後通過「查找」（find）和「合併」（union）操作來動態地管理這些集合。

具體步驟如下：

  1. 初始化：將每個節點自成一個集合，並維護一個父節點陣列 papa 來表示每個節點所屬的集合。此外，為了優化合併操作和追蹤集合大小，可以使用一個大小陣列 szsz 用來記錄每個集合的大小，並在合併時使用按大小合併（Union by Size），這裡也可以使用按秩合併（Union by Rank），但我比較習慣使用前者。
  2. 遍歷邊：對於圖中的每一條邊 (x,y)(x, y)，我們使用 find 函數分別查找節點 xx 和節點 yy 所屬的集合。如果 xx 和 yy 已經在同一個集合中，這表示添加這條邊會形成一個循環，即這條邊是多餘的，應該返回該邊作為答案。
  3. 合併集合：如果 xx 和 yy 不在同一個集合中，則將它們所屬的集合合併為一個集合。在合併時，我們使用「按大小合併」（Union by Size）的策略，即將較小的集合合併到較大的集合中，從而優化後續的查找操作效率。
  4. 返回結果：遍歷完所有邊後，如果沒有發現形成循環的邊，則返回空列表。不過根據題意，至少會有一條多餘的邊，因此實際上會在遍歷過程中找到並返回這條邊。

複雜度分析

  • 時間複雜度：O(α(n)⋅n)\mathcal{O}(\alpha(n) \cdot n)，其中 nn 是邊的數量，α(n)\alpha(n) 是阿克曼函數的反函數，可以視為常數。
  • 空間複雜度：O(n)\mathcal{O}(n)。
    • 需要額外的空間來存儲父節點陣列 papa 和大小陣列 szsz，每個陣列的大小都是 O(n)O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        pa = list(range(n + 1))
        sz = [1] * (n + 1)

        def find(x):
            if pa[x] != x:
                pa[x] = find(pa[x])
            return pa[x]
            
        for x, y in edges:
            fx, fy = find(x), find(y)
            if fx == fy: # 已經在同一個集合
                return [x, y]
            if sz[fx] > sz[fy]: # Union by size
                fx, fy = fy, fx
            pa[fy] = fx
            sz[fx] += sz[fy]
        return []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> pa(n + 1);
        vector<int> sz(n + 1, 1);
        for (int i = 0; i < n + 1; ++i) pa[i] = i;

        function<int(int)> find = [&](int x) -> int {
            if (pa[x] != x) pa[x] = find(pa[x]);
            return pa[x];
        };

        for (auto& e : edges) {
            int fx = find(e[0]), fy = find(e[1]);
            if (fx == fy) return e;
            if (sz[fx] > sz[fy]) swap(fx, fy);
            pa[fy] = fx;
            sz[fx] += sz[fy];
        }
        return {};
    }
};

寫在最後

PROMPT

Mystical Moonlight Encounter: A young anime girl, dressed in a black cape and witch hat, holds a pumpkin with an intense gaze. Standing before a large window framing a moonlit night sky, her focus is riveted on the pumpkin. To her left, a vibrant yellow pumpkin sits atop a straw bale amidst autumn leaves, adding a burst of warmth to the enchanting scene.