Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

1319. Number of network access operations

Ethernet cables are used to connect n computers, numbered from 0 to N-1, into a network. Connections [I] = [a, B] Connects computers A and B.

Any computer on the network can directly or indirectly access any other computer on the same network.

To give you the initial wiring connections for this computer network, you can unplug any cable between two directly connected computers and use it to connect a pair of not directly connected computers. Please calculate and return the minimum number of operations required to get all computers connected. If that is not possible, -1 is returned.

 

Example 1:

Input: n = 4, connections = [[0,1],[0,2]] output: 1 description: unplug the cable between computers 1 and 2, and plug it into computers 1 and 3.Copy the code

Example 2:

Input: n = 6, connections = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]] output: 2Copy the code

Example 3:

Input: n = 6, connections = [[0, 1], [0, 2], [0, 3], [1, 2]] output: 1: cable shortage.Copy the code

Example 4:

Input: n = 5, connections = [[0, 1], [0, 2], [3, 4], [2, 3]] output: 0Copy the code

 

Tip:

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] ! = connections[i][1]
  • There are no duplicate connections.
  • Two computers are not connected by multiple cables.

Train of thought

This topic is a typical query set questions, if you are not clear what is the query set can first look at my article: JS in the query set

  1. So let’s make a judgment. Let’s linknA computer, at leastn - 1It takes a cable to make sure it’s all connected, so ifconnectionsThe length is not enoughn - 1, indicating not enough to link all computers, return- 1;
  2. We can do a loop to see if there is a connection between the two computers, and if there is, we can repeat it, but the problem doesn’t say we can’t repeat it, so we can just ignore it and wait until it’s not connected enough to disassemble the repeated line;
  3. If two elements have not been linked before, they are valid links. Add one to the number of valid links, and then associate the two elements.
  4. At the end of the loop, returnN-1 - Number of valid linksCan.

implementation

/ * * *@param {number} n
 * @param {number[][]} connections
 * @return {number}* /
var makeConnected = function(n, connections) {
    const len = connections.length;
    // At least n-1 wires are required
    if (n - 1 > len) return -1;

    // Determine how many valid links there are
    let count = 0;
    const uf = new UnionFind(len);

    for (let i = 0; i < len; i++) {
        let [ a, b ] = connections[i];

        // If they are already connected, the link is invalid
        // Otherwise, the link is valid and the relationship is established
        if (uf.find(a) !== uf.find(b)) {
            uf.merge(a, b);
            count++;
        } 
    }

    // To link n elements, only n-1 valid links are required
    return n - 1 - count;
};

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.