# Topic

Alice and Bob share an undirected graph, which contains n nodes and three types of edges

Type 1: can only be traversed by Alice.

Type 2: can only be traversed by Bob.

Type 3: both Alice and Bob can traverse.

Give you an array edges, where edges[i] = [typei, ui, vi] indicates that there are two-way edges of type I between nodes ui and VI. Please find out the maximum number of edges that can be deleted on the premise that the graph can still be completely traversed by Alice and Bob. If Alice and Bob can reach all other nodes from any node, the graph is considered to be completely ergodic.

Returns the maximum number of edges that can be deleted, and - 1 if Alice and Bob cannot traverse the graph completely.

# Example

## Example_1

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 you delete [1,1,2] and [1,1,3], Alice and Bob can still traverse the graph completely. Deleting any other edges does not guarantee that the graph can be completely traversed. So the maximum number of edges that can be deleted is 2.

## Example_2

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]

Output: 0

Explanation: note that deleting any edge will prevent Alice and Bob from completely traversing the graph.

## Example_3

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 other nodes. Similarly, Bob cannot reach node 1. Therefore, the graph cannot be completely traversed.

# Tips

1 <= n <= 10^5

1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)

edges[i].length == 3

1 <= edges[i][0] <= 3

1 <= edges[i][1] < edges[i][2] <= n

All tuples (type I, UI, VI) are different from each other

# Solution

The title is very interesting. It's not difficult to understand

Template based on size optimized union search template Implementation (click to view)

## Connection type 3 is preferred

First of all, it is not difficult to see that the utilization efficiency of type 3 is actually higher

Priority should be given to connecting common edges

As a common edge:

(it is assumed that all edges will be used in the discussion)

When it's used to connect

If it is used by both sides, its utilization efficiency will be higher than that of one side

(other types of edges are used only once, but common edges are used twice)

If it's only used by Alice or Bob

Its utilization efficiency will be the same as Type1 or Type2 (can be regarded as word utilization side)

(used only once)

Therefore, to sum up:

The common edge is likely to be used more efficiently (twice)

Even if it can not be used twice, its efficiency is the same as that of single use

Considering the common edge utilization efficiency of type 3 is likely to be higher

You need to give priority to connecting edges of type 3

## And look up the set to judge the connection

After that, we will consider and collect some old and common questions

Q: how to use union search to indicate that a node has been connected?

A: if all nodes are in the same connection component, all nodes are connected

Q: how to judge whether two nodes are connected?

A: two nodes are in the same connected component (the root node is the same)

Q: how to judge whether all nodes are connected?

A: num is initialized in advance to calculate the connected components

When add, the connected component + = 1

When merge, the connected component - = 1

## Start judging

Initialize res as the result and num as the number of connected components

We need to judge Alice and Bob separately

When judging the common edge, uf_A and uf_B same

Connect the common edge first (type 3):

If the common edge connects two nodes, the two nodes are not connected

You must connect the two nodes with a common edge

Connect the two nodes on this side

If the common edge connects two nodes, the two nodes are connected

You do not need to connect the common edge

At the same time, res += 1

(res is in merge)

And then to uf_A and UF_ The edge of B is judged separately

If this edge connects two nodes, the two nodes are not connected

You must use this edge to connect the two nodes

Connect the two nodes on this side

If this edge connects two nodes, the two nodes are connected

You do not need to connect this side

At the same time, res += 1

Finally, we need to judge whether Alice and Bob are connected

If one party is not connected (num is larger than 1), then - 1 is returned

If they are both connected, then the number of deleted edges ans in a common node is returned by adding the two res

(ans calculated twice)

# Code

class UnionFind: def __init__(self): self.father = {} self.size = [1] self.num = 0 # Initialize the connected component to 0 self.res = 0 # Initialization result res def find(self, x): root = x while self.father[root] is not None: root = self.father[root] # Path compression while x != root: original_father = self.father[x] self.father[x] = root x = original_father return root def merge(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x == root_y: self.res += 1 # If the condition is not satisfied, the edge is not needed return False else: if self.size[root_x] < self.size[root_y]: root_x, root_y = root_y, root_x self.size[root_x] += self.size[root_y] self.father[root_x] = root_y self.num -= 1 # Connected components after merging - 1 def add(self, x): if x not in self.father: self.father[x] = None self.size.append(1) self.num += 1 # Every additional node connected component + 1 class Solution: def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int: uf_A = UnionFind() # Initialization and lookup A uf_B = UnionFind() # Initialize and search set B for i in range(1, n + 1): uf_A.add(i) # Add a node to the query set uf_B.add(i) for j in edges: if j[0] == 3: uf_A.merge(j[1], j[2]) uf_B.merge(j[1], j[2]) ans = uf_A.res # Record the number of common edge deletions for x in edges: if x[0] == 1: # To judge Alice uf_A.merge(x[1], x[2]) if x[0] == 2: # Judge Bob uf_B.merge(x[1], x[2]) if uf_A.num != 1 or uf_B.num != 1: return -1 return uf_A.res + uf_B.res - ans # Since the deleted common edge is calculated twice, one must be subtracted