[B] [C] [D]

A tree can be thought of as a connected and acyclic undirected graph.

Given the graph after adding an edge to a tree with n nodes (values 1 to n). The two vertices of the added edge are contained between 1 and n, and the added edge does not belong to an existing edge in the tree. Edges [I] = [ai, bi] indicates that there is an edge between AI and BI in the graph.

Find an edge that can be deleted so that the remainder is a tree with n nodes. If there are more than one answer, the last edge present on the array edges is returned.

Example 1:

Edges input: edges = [[1,2], [1,3], [2,3]Copy the code

Example 2:

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] output: [1, 4]Copy the code

Tip:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai ! = bi
  • edgesThere is no repeating element in
  • The given graph is connected

Their thinking

In this case, you need to find redundant connections. If a connection is not connected, all nodes are still connected. So you can iterate through the input array and merge two nodes into a set. If you walk through an edge and the two nodes are already in the same set, that edge is an edge that can be deleted. So in this process we need to get the set of elements and merge the set of two elements. For this kind of problem, you can use a look-up set to solve the problem. If you do not understand and search set, you can see my article data structure – and search set, the paper introduces the concept of and search set, application scenarios and handwritten implementation of the whole process.

Code implementation

This. size = Array(n).fill(1); This. list = Array(n) for(let I = 0; i<n; i++){ this.list[i] = i; Find (x){if(this.list[x]===x) return x; Const root = this.find(this.list[x]) // Mount the current node as the root node, this.list[x] = root; return root; Const rootA = this.find(a), rootB = this.find(b); // Merge merge(a,b) const rootA = this.find(a), rootB = this.find(b); If (rootA===rootB) return; if(rootA== rootB) return; If (this.size[rootA]>this.size[rootB]){this.list[rootB] = rootA; // If (this.size[rootA]>this.size[rootB]){this.list[rootB] = rootA; Size [rootA] += this.size[rootB]}else{// If (rootA = rootB) {this.list[rootA] = rootB; Size [rootB] += this.size[rootA]}} var findRedundantConnection = function(edges) {// Obtain the number of edges const len = Edges. Length, // create a new unionset = new unionset (len+1); For (let I = 0; i<len; I ++){const [a,b] = edges[I]; If (ononset. Find (a)=== ononset. Find (b)) return [a,b] // Ononset.Copy the code

At this point we have leetcode-684-redundant join

If you have any questions or suggestions, please leave a comment!