[B] [C] [D]
In this problem, a rooted tree is a directed graph that satisfies the following conditions. There is only one root node in the tree, and all other nodes are heirs of that root node. Every node in the tree except the root node has one and only one parent, and the root node has no parent.
Enter a directed graph consisting of a tree with n nodes (values 1 through n are not duplicated) and an additional directed edge. The additional edge is contained between two different vertices between 1 and n, and does not belong to an existing edge in the tree.
The resulting graph is a two-dimensional array of edges. Each element is a pair of [UI, vi] to represent edges in a directed graph that connect vertex UI to vertex vi, where UI is a parent node of vi.
Returns an edge that can be deleted, leaving the graph as a root tree with n nodes. If there are multiple answers, return the last answer to appear in the given two-dimensional array.
Example 1:
Edges input: edges = [[1,2],[1,3],[2,3]Copy the code
Example 2:
Input: edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] output: (4, 1)Copy the code
Tip:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n
Their thinking
It’s still a connectivity problem, but it’s complicated by adding directivity to connectivity. In this case, the connection mode of a directed graph can be divided into three types, and its return value should be discussed according to the classification of the connection mode.
- The connection case in example 1, where a child node has two parents, is defined as a double-entry case
- The join case in Example 2, where the join forms a loop, is defined as a loop case
- The case not given in the example is the case of loop formation and double entry
In the case of double intakes, the edge that needs to be returned is the edge that forms the double intakes. For the loop-forming case, the edges that need to be returned are the loop-forming edges. In the case of ring formation and double entry, we need to return the edge composed of the child node of the double entry edge and its parent node.
The demo
Code implementation
Constructor (n){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]) this.list[x] = root; return root; } merge(rootA,rootB){this.list[rootB] = rootA; // Merge (rootA,rootB){this.list[rootB] = rootA; }} var findRedundantDirectedConnection = function (edges) {/ / get number vertex const len = edges. The length, Ononset = new ononset (len+1); ononset = new ononset (len+1); ononset = new ononset (len+1); for(let i = 1; i<=len; i++){ parent[i] = i; } // let doubleInd = -1,circleInd = -1; // iterate over the input array for(let I = 0; i<len; i++){ const [a,b] = edges[i]; // If (parent[b]! ==b) doubleInd = i; Else {// otherwise update the child's parent[b] = a; Find (a), rootB = unionset. Find (b); if(rootA===rootB) circleInd = i; Ononset (rootA,rootB)}} ononset (rootA,rootB)}} If (doubleInd===-1) return edges[circleInd] // If only the circleInd edges, If (circleInd===-1) return edges[doubleInd] // If circleInd===-1) return edges const Child = edges[doubleInd][1]; return [parent[child],child] };Copy the code
At this point we are done with Leetcode-685-Redundant join II
If you have any questions or suggestions, please leave a comment!