# LC 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

### [Problem link](https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/)

###### tags: `leedcode` `python` `hard` `Union Find`

Alice and Bob have an undirected graph of <code>n</code> nodes and three types of edges:

- Type 1: Can be traversed by Alice only.
- Type 2: Can be traversed by Bob only.
- Type 3: Can be traversed by both Alice and Bob.

Given an array <code>edges</code> where <code>edges[i] = [type_i, u_i, v_i]</code> represents a bidirectional edge of type <code>type_i</code> between nodes <code>u_i</code> and <code>v_i</code>, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return <code>-1</code> if Alice and Bob cannot fully traverse the graph.

**Example 1:**

**<img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/ex1.png" style="width: 179px; height: 191px;" />**

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

**Example 2:**

**<img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/ex2.png" style="width: 178px; height: 190px;" />**

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

**Example 3:**

**<img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/ex3.png" style="width: 178px; height: 190px;" />**

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

**Constraints:**

- <code>1 <= n <= 10⁵</code>
- <code>1 <= edges.length <= min(10⁵, 3 * n * (n - 1) / 2)</code>
- <code>edges[i].length == 3</code>
- <code>1 <= type_i <= 3</code>
- <code>1 <= u_i < v_i <= n</code>
- All tuples <code>(type_i, u_i, v_i)</code> are distinct.

## Solution 1 - Union Find

class UnionFind:
    def __init__(self, size):
        self.root = list(range(size + 1))
        self.rank = [1] * (size + 1)
        self.size = size
        self.lineCount = 0

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootY] > self.rank[rootX]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1
            self.lineCount += 1

    def isAllConnect(self):
        return self.lineCount == self.size - 1

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        edge1 = []
        edge2 = []
        edge3 = []

        for type_, start, end in edges:
            if type_ == 3:
                edge3.append([start, end])
            elif type_ == 1:
                edge1.append([start, end])
            else:
                edge2.append([start, end])

        alice_uf = UnionFind(n)
        bob_uf = UnionFind(n)

        for start, end in edge3:
            alice_uf.union(start, end)
            bob_uf.union(start, end)

        count3 = alice_uf.lineCount

        for start, end in edge1:
            alice_uf.union(start, end)

        if not alice_uf.isAllConnect():
            return -1

        for start, end in edge2:
            bob_uf.union(start, end)

        if not bob_uf.isAllConnect():
            return -1

        return len(edges) - alice_uf.lineCount - bob_uf.lineCount + count3

>### Complexity
>n = max(number of nodes, edges.length)
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
結論: 好難 ==
一開始在Alice與Bob的生成樹都不是唯一的這件事上苦惱很久, 後來去看了官神的yt就懂了.
**" 將Alice與Bob分開來看 "**
[官神 yt](https://www.youtube.com/watch?v=AplZXP_LxgU)
[c++ code](https://github.com/wisdompeak/LeetCode/blob/master/Union_Find/1579.Remove-Max-Number-of-Edges-to-Keep-Graph-Fully-Traversable/1579.Remove-Max-Number-of-Edges-to-Keep-Graph-Fully-Traversable.cpp)
>1. 先計算type3的邊最少需要幾條.

for start, end in edge3:
    alice_uf.union(start, end)
    bob_uf.union(start, end)

count3 = alice_uf.lineCount

>2. 再分別計算最少需要幾條type1與type2的邊讓Alice與Bob的所有Node連接起來. 假如全部type1的邊不足以讓Alice的所有Node連接起來, return -1, Bob也是.

for start, end in edge1:
    alice_uf.union(start, end)

if not alice_uf.isAllConnect():
    return -1

for start, end in edge2:
    bob_uf.union(start, end)

if not bob_uf.isAllConnect():
    return -1

>3. 全部會用到的邊的數量為 alice_uf.lineCount + bob_uf.lineCount - count3 = x, 最後return多餘的邊為 len(edges) - x.

return len(edges) - alice_uf.lineCount - bob_uf.lineCount + count3