題目網址：https://leetcode.cn/problems/redundant-connection/

題意：給一 n 個 node 的 tree（編號從 1 到 n）, 並在其中添加一條邊。添加的邊其兩個頂點包含在 1 到 n 中間, 且這條邊不屬於 tree 中已存在的邊。edges[i] = [a, b] 表示圖中 a 和 b 之間存在一條邊。

找出一條可以刪去的邊, 刪除後可使得剩餘部分為 tree。如果有多個答案, 則返回這些答案在 edges 中順序最後的那條邊。

Solution 1：

想法：同 261. Graph Valid Tree, 利用 DFS, 每次加入一條 edge e, 就檢查是否有 cycle, 一旦發現了 cycle, 就返回 e（最後加入形成 cycle 的 edge）

  • 令 e 的兩端點分別為 u、v, 檢查是否已經有 path 能連接 u、v。若有, 則代表加入 e 後會形成 cycle
  • 由於為無向圖, 所以遞迴遍歷時需要用 visited 紀錄哪些 node 已經拜訪過, 一旦拜訪過就不再遞迴遍歷。假設 edge e = [u,v], 則 u、v 之間並無 cycle, 若不用 visited 紀錄, 則會發生 u -> v、v -> u, 因而得出 u、v 之間存在 cycle 的錯誤判斷。
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for (const auto& e : edges) {
            unordered_set<int> visited;

            if (hasPath(e[0], e[1], visited)) {
                return e;
            }

            // 加入 e
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }

        return {};
    }

private:
    unordered_map<int, vector<int>> adj; // adjacent list

    // 若 cur 能走到 goal, 則返回 true
    bool hasPath(const int cur, const int goal, unordered_set<int>& visited){
        if (cur == goal) {
            return true;
        }

        visited.emplace(cur);

        // 其中一個點不在 adj 中, 則一定找不到 path 連接兩點
        if (adj.find(cur) == adj.end() || adj.find(goal) == adj.end()) {
            return false;
        }

        for (const auto& next : adj[cur]) {
            if (visited.find(next) != visited.end()) {
                continue; // 已經拜訪過則跳過
            }

            if (hasPath(next, goal, visited)) {
                return true;
            }
        }
        return false;
    }
};
  • time：$O(n^2)$ ➔ 其中 n 代表 edge、node 數
    • $O(n^2)$：worse case 對於每次新增的 edge e, 必須搜索圖中之前出現的每條 edge
      ➔ $1 + 2 + … + n$ = $\dfrac{(n + 1) \cdot n}{2}$
  • space：$O(n)$ ➔ adj 的 avg case 為 $O(V + E)$, 本題的 V、E 皆為 n（因為是 tree + 1 edge）

Solution 2：

想法：同 261. Graph Valid Tree, 利用 Union Find + Path Compression, 用 Union Find 合併每條邊的兩個 node 時, 如果這兩個 node 已經在同一 set 中, 則存在 cycle

e.g. edges = [[1,2], [1,3], [2,3]]

  • 當完成 [1,2] 和 [1,3] 時, parents[2] = 1 = parent[3]
  • 然後執行 [2,3] 時, 因為 parents[2] == parents[3] 代表有 cycle
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parents(n + 1, 0); // 紀錄每個點的 parent
        vector<int> ranks(n + 1, 1); // 紀錄每個點的 rank

        // 每個點的 parent 都初始成自己
        for (int i = 1; i <= n; ++i) {
            parents[i] = i;
        }

        for (const auto& e : edges) {
            const int r1 = find(parents, e[0]); // root of a
            const int r2 = find(parents, e[1]); // root of b

            // a, b 已經是同個 set, 則代表加入 e 後會形成 cycle
            if (r1 == r2) {
                return e;
            }

            // a, b 是不同 set, 則兩個 set 合併成一個 set
            union_(parents, ranks, r1, r2);
        }
        return {};
    }

private:
    int find(vector<int>& parents, int i){
        while (i != parents[i]) {
            parents[i] = parents[parents[i]];
            i = parents[i];
        }
        return i;
    }

    void union_(vector<int>& parents, vector<int>& ranks, int& r1, int& r2){
        // 深度低的 tree root 把深度高的 tree root 作為 parent
        if (ranks[r1] > ranks[r2]) {
            parents[r2] = r1;
        } else if (ranks[r1] < ranks[r2]) {
            parents[r1] = r2;
        } else { // 若深度一樣, 可以任意選擇一個 root 作為 parent
            parents[r2] = r1;
            ++ranks[r1]; // 作為 parent 的 node 之 rank 值會加一, 因為深度變了
        }
    }
};
  • time：$O(n)$ ➔ 遍歷每個 node 初始化 parents, 以及遍歷每條 edge 做 union find, 而 edge 的兩端點做 find() 皆只需 $O(1)$, 其中 node、edge 數皆為 n
  • space：$O(n)$ ➔ parent, ranks