🔗 🔴 685. Redundant Connection II

tags: `圖(Graph)` `DFS` `BFS` `併查集(Union Find)`

題意

在本題中，樹被認為是一個有向圖，它存在且僅有一個根節點，所有其他節點都是根節點的子孫(descendant)，並且除了根節點沒有父節點以外，每個節點都有且僅有一個父節點。

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

返回可以刪除的一條邊，以使得結果圖是一棵有 $n$ 個節點的樹。如果有多個答案，返回在二維陣列中出現的最後一個答案。

思路：併查集(Union Find)

由於題目是在一棵有向樹中添加一條邊，我們可以先假設多餘的邊為 $(u, v)$ ，則有以下 3 種情況：

$v$ 是根節點，此時會出現環，但 $v$ (節點 $1$ ) 只有 1 個父節點

Case1

$v$ 是 $u$ 除了根節點以外的某個祖先，此時會出現環，且 $v$ (節點 $2$ ) 存在 2 個父節點

Case2

其餘情況，此時 $v$ (節點 $2$ ) 也會有 2 個父節點，但沒有形成環

Case3

對於 Case 1，我們可以如同 684. Redundant Connection 一樣，使用併查集來解決。但這題的難點在於如何區分 Case 2 和 Case 3。

注意到 Case 2 和 Case 3 中都會有一個節點有兩條入邊，且這兩條入邊之一即為答案。因此我們可以先遍歷所有邊，記錄每個節點的入邊索引，若某個節點有兩條入邊 $edges[i_1], edges[i_2]$ ，則該節點即為 Case 2 或 Case 3 的節點，我們可以標記該節點。

在 Case 2 中，我們需要刪除的是會形成環的那條入邊。
在 Case 3 中，兩條入邊都可以被刪除，但根據題意，我們需要刪除的是第二條入邊 $edges[i_2]$ 。

由於只有 $2$ 個選項，我們可以先假設要刪除的是第二條入邊 $edges[i_2]$ ，並先忽略該條邊，如此便可以轉換為無向圖的連通性問題。

在遍歷除了 $edges[i_2]$ 以外的所有邊時若可以形成環，則說明是 Case 2，且需要刪除指向 $mark$ 的第一條邊；
若無法形成環，則可以是 Case 2 或 Case 3，但不管如何，答案都是 $edges[i_2]$ $e d g es [i_{2}]$ 。
- 如果是 Case 2，因為在上述過程中我們確定了 $edges[i_1]$ 不會形成環，因此答案只能是 $edges[i_2]$

具體步驟如下：

反向圖建構：首先，我們建立一個反向圖 $rg$ ，用來記錄每個節點的入邊，且使用一個變數 $mark$ 用來標記是否存在節點有兩個父節點的情況，初始化為 $-1$ 。
檢查是否有節點有兩個父節點：遍歷所有邊，將每條邊的終點記錄在反向圖中。如果某個節點有兩條入邊，則將其記錄在 $mark$ 中。
使用併查集檢測是否有環：
- 初始化併查集，將每個節點的父節點設為自己。
- 再次遍歷除了指向 $mark$ 的第二條邊以外的所有邊，對於每一條邊，嘗試將其連接的兩個節點進行併集合併。
- 如果在合併過程中發現兩個節點已經在同一個集合中，則說明存在環路。
  - 此時若 $mark$ 為 $-1$ ，則說明是 Case 1，返回形成環路的那條邊。
  - 否則代表是 Case 2，返回指向 $mark$ 的第一條邊。
若遍歷完所有邊後仍無法形成環路，則代表是 Case 3，返回指向 $mark$ 的第二條邊。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \alpha(n))$ $O (n \cdot α (n))$ ，其中 $n$ $n$ 是節點數量， $\alpha(n)$ $α (n)$ 是阿克曼函數的反函數，可以視為常數。
- 遍歷所有邊以構建反向圖： $O(n)$
- 併查集操作： $O(n \cdot \alpha(n))$
空間複雜度： $\mathcal{O}(n)$ $O (n)$ ，其中 $n$ $n$ 是節點數量。
- 反向圖： $O(n)$
- 併查集： $O(n)$

class UnionFind:
    __slots__ = ['n', 'pa', 'sz']

    def __init__(self, n: int):
        self.n = n
        self.pa = list(range(n)) # 父節點
        self.sz = [1] * n # 連通分量大小

    def find(self, x: int) -> int:
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]
    
    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.sz[px] < self.sz[py]:
            px, py = py, px
        self.pa[py] = px
        self.sz[px] += self.sz[py]
        return True
    
class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        rg = [[] for _ in range(n + 1)] # 反圖
        mark = -1 # 記錄有兩個父節點的節點
        for idx, (u, v) in enumerate(edges):
            rg[v].append(idx) # 記錄節點 v 的邊索引
            # 出現 Case 2 或 Case 3
            if len(rg[v]) == 2:
                mark = v
        uf = UnionFind(n + 1)
        for i, (u, v) in enumerate(edges):
            # 出現 Case 2 或 Case 3，此時跳過指向 mark 的第二條邊
            if mark != -1 and i == rg[mark][1]:
                continue
            if not uf.union(u, v): # 有環
                if mark == -1: # Case 1
                    return edges[i]
                else: # Case 2a
                    return edges[rg[mark][0]]
        # Case 2b or Case 3
        return edges[rg[mark][1]]

class UnionFind {
public:
    vector<int> pa, sz;
    int cnt;
    UnionFind(int n) {
        pa.resize(n);
        iota(pa.begin(), pa.end(), 0);
        sz.assign(n, 1);
        cnt = n;
    }
    int find(int x) {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }
    bool unionSet(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x;
        sz[x] += sz[y];
        cnt--;
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<vector<int>> rg(n + 1); // 反圖
        int mark = -1; // 記錄有兩個父節點的節點
        for (int i = 0; i < n; i++) {
            int u = edges[i][0], v = edges[i][1];
            rg[v].push_back(i); // 記錄節點 v 的邊索引
            if (rg[v].size() == 2) mark = v; // 出現 Case 2 或 Case 3
        }
        UnionFind uf(n + 1);
        for (int i = 0; i < n; i++) {
            int u = edges[i][0], v = edges[i][1];
            // 出現 Case 2 或 Case 3，此時跳過指向 mark 的第二條邊
            if (mark != -1 && i == rg[mark][1]) continue;
            if (!uf.unionSet(u, v)) { // 有環
                if (mark == -1) return edges[i]; // Case 1
                else return edges[rg[mark][0]]; // Case 2a
            }
        }
        return edges[rg[mark][1]]; // Case 2b or Case 3
    }
};