🔗 🔴 1579. Remove Max Number of Edges to Keep Graph Fully Traversable 2132

tags: `Weekly Contest 205` `併查集(Disjoint Set)` `圖(Graph)` `DSU`

題意

Alice 和 Bob 可以在一個無向圖上行走，其中包含 $n$ 個節點和 $3$ 種類型的邊：

類型 $1$ ：只有 Alice 可以走。
類型 $2$ ：只有 Bob 可以走。
類型 $3$ ：Alice 和 Bob 都可以走。

給定一個陣列 $\text{edges}$ ，其中 $\text{edges}[i] = [\text{type}_i, u_i, v_i]$ 表示類型為 $\text{type}_i$ 的雙向邊連接節點 $u_i$ 和 $v_i$ ，找出可以移除的最大邊數，使得移除後，圖仍然可以被 Alice 和 Bob 完全遍歷。如果從任何一個節點開始，Alice 和 Bob 都可以到達所有其他節點，則圖被 Alice 和 Bob 完全遍歷。

返回你可以移除的最大邊數，如果 Alice 和 Bob 不能完全遍歷整個圖則返回 $-1$ 。

思路：DSU(Disjoint Set Union)

題意的要求是移除最大數量的邊，使得整個圖是連通的，而求連通分量的問題可以使用併查集(DSU) 來解決，分別對 Alice 和 Bob 創建兩個 DSU 類別，然後對於每條邊進行合併操作。

但由於有三種類型的邊，我們需要對邊進行分類，分別處理公共的邊、Alice 的邊和 Bob 的邊。首先，我們將給定的邊分為三組：公共的邊、Alice 的邊和 Bob 的邊。

首先處理公共的邊，即類型為 $3$ 的邊。如果其中一個人無法成功合併這條邊，則代表該條鞭可以被移除，需要增加答案計數。
然後處理 Alice 的邊和 Bob 的邊，同理，如果其中一個人無法成功合併那條邊，則代表該條鞭可以被移除，需要增加答案計數。

最後需要檢查兩個人的 DSU 是否都只有一個連通分量，如果是則返回答案，否則表示有多個連通分量，無法連通，返回 $-1$ 。

複雜度分析

時間複雜度： $O(m \cdot \alpha(n))$ ，其中 $m$ 為邊數， $\alpha(n)$ 為 Ackermann 函數的反函數。
空間複雜度： $O(n)$

class DSU: # Disjoint Set Union
    __slots__ = ['n', 'pa', 'sz', 'cnt']

    def __init__(self, n: int):
        self.n = n
        self.pa = list(range(n)) # 父節點
        self.sz = [1] * n # 連通分量大小
        self.cnt = 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]
        self.cnt -= 1
        return True

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        lst = [[] for _ in range(3)]
        for t, u, v in edges:
            lst[t-1].append((u-1, v-1))
        ans = 0
        uf1, uf2 = DSU(n), DSU(n)
        for u, v in lst[2]: # Common
            if not uf1.union(u, v) or not uf2.union(u, v):
                ans += 1
        for u, v in lst[0]: # Alice
            if not uf1.union(u, v):
                ans += 1
        for u, v in lst[1]: # Bob
            if not uf2.union(u, v):
                ans += 1
        return ans if uf1.cnt == 1 and uf2.cnt == 1 else -1

class DSU {
public:
    vector<int> pa, sz;
    int cnt;
    DSU(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:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> lst(3);
        for (auto& e : edges){
            lst[e[0]-1].emplace_back(e[1]-1, e[2]-1);
        }
        int ans = 0;
        DSU uf1(n), uf2(n);
        for (auto& e : lst[2]){
            int u = e.first, v = e.second;
            if (!uf1.unionSet(u, v) || !uf2.unionSet(u, v))
                ans++;
        }
        for (auto& e : lst[0]){
            int u = e.first, v = e.second;
            if (!uf1.unionSet(u, v))
                ans++;
        }
        for (auto& e : lst[1]){
            int u = e.first, v = e.second;
            if (!uf2.unionSet(u, v))
                ans++;
        }
        return uf1.cnt == 1 && uf2.cnt == 1 ? ans : -1;
    }
};