“This is the 39th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Leetcode-685 Redundant connection II

Subject to introduce

See the link above for the original topic

Their thinking

If we add an edge to a normal tree, let’s see what happens when we add a directed edge to a tree

  1. In the first case, the extra edge points to a node that already has a parent node, but after adding an edge, the node has two parents, resulting in a conflict

  1. In the second case, the redundant edges point to the root node, causing each node in the tree to have a parent node, thus forming a ring

  1. The third case is a combination of the previous two cases, where the extra edge points to a node, forming both a ring and a node with two parent nodes

Adding a directed edge to an entire tree is one of the three ways to do it. Here’s how it works:

  1. For the first case, we connect nodes according to the order of edges given by the question (record the parent node of each node). When the node pointing to an edge already has a parent node, it means that this edge is a conflicting edge and can be directly returned to this edge
  2. For the second case, we first use the idea of searching sets to connect the nodes of each edge given by the problem. When traversing an edge, the nodes at both ends of the edge already exist in the same set, it means that this edge is the edge that forms the ring and is the last edge, so we can directly return to this edge
  3. For the third case, you need to combine the previous two cases.
  • First we iterate over each edge, and if it’s not a conflicting edge, we connect the nodes at both ends of the edge
  • If the edge is in conflict, the subscript of this edge is recorded, and then the parent node of the current node is not updated, and the next edge is judged. When the edge forming a ring appears, the subscript of the current edge forming a ring is recorded
  • At this time, because the conflicting edges are not connected, but there is a ring edge, indicating that the additional edge is the red edge in the figure, how to find this edge? (Parent of the parent of the looped edge -> parent of the looped edgeThis side of the

The problem solving code

var findRedundantDirectedConnection = function(edges) {
    const unionSet = new UnionSet(edges.length + 1)
    // Record the parent of each node
    const father = []
    for (let i = 1; i <= edges.length; i++) {
        father[i] = i
    }

    // Record the subscripts of the conflicting edges
    let conflict = -1
    // Record the index of the ring's edge
    let cycle = -1
    for (let i = 0; i < edges.length; i++) {
        const node1 = edges[i][0], node2 = edges[i][1]
        if(father[node2] ! == node2) {// If there are conflicting edges, only the subscript is recorded
            conflict = i
        } else {
            // If there is no conflicting edge, record the parent node first, then determine whether the ring is formed
            father[node2] = node1
            if (unionSet.get(node1) === unionSet.get(node2)) {
                cycle = i
            } else {
                unionSet.merge(node1, node2)
            }
        }
    }
    
    if (conflict === -1) {
        // If there are no conflicting edges, the looped edge is an added-edge
        return edges[cycle]
    } else {
        if (cycle > -1) {
            // If there are both ringed edges and appended edges, then the edge is' parent of the parent of the ringed edge -> parent of the ringed edge '
            return [father[edges[conflict][1]], edges[conflict][1]]}else {
            // If there are no ring edges, then the conflicting edges are added-edges
            return edges[conflict]
        }
    }
};

/ / and set
class UnionSet{
    constructor(n) {
        this.fa = []
        this.size = []
        for (let i = 0; i < n; i++) {
            this.fa[i] = i
            this.size[i] = 1}}get(v) {
        if (this.fa[v] === v) return v
        const root = this.get(this.fa[v])
        this.fa[v] = root
        return root
    }

    merge(a, b) {
        const ra = this.get(a), rb = this.get(b)
        if (ra === rb) return 
        if (this.size[ra] < this.size[rb]) {
            this.fa[ra] = rb
            this.size[rb] += this.size[ra]
        } else {
            this.fa[rb] = ra
            this.size[ra] += this.size[rb]
        }
    }
}
Copy the code