“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022”

Leetcode-1319 Number of operations performed to connect to the network

Subject to introduce

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

Enter n =4, connections = [[0.1], [0.2], [1.2]] output:1Explanation: Unplug the computer1 和 2Between the cable and plug it into the computer1 和 3On.Copy the code

Example 2

Enter n =6, connections = [[0.1], [0.2], [0.3], [1.2], [1.3]] output:2
Copy the code

Example 3

Enter n =6, connections = [[0.1], [0.2], [0.3], [1.2] Output: -1Description: The number of cables is insufficient.Copy the code

Example 4

Enter n =5, connections = [[0.1], [0.2], [3.4], [2.3]] output:0
Copy 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.

Their thinking

If n computers are connected by cable to form a network, so that any two computers can access each other directly or indirectly, the minimum number of cables required is N-1, and each connections[I] given in the question represents a cable, so we can conclude that the operation is impossible. Connections. length < n-1, meaning there are not enough cables

So how to determine the minimum number of operations, see the following figure



Looking at the example in example 1, the connectivity between computers takes this4The computer split2So if we want to connect these two sets, at least we need to1One cable, so the minimum number of operations is1



In the example of example 2, the connectivity of the computers divides the computers3I’m going to take this3To connect, at least2One cable, therefore, the minimum number of operations is2

After the above analysis, in fact, the solution is obvious. First, calculate how many sets n are divided into all computers according to the connection relation of cables given in the problem. Then, the minimum number of times to connect these sets is N-1

We can solve this problem by using and looking up sets

The problem solving steps

  1. judgeconnectionsIs the array length less than the number of computers – 1 (n - 1)
  2. Define a look-up set, size is the number of computersn
  3. traverseconnectionsArray to connect two computers in each array traversed
  4. Count and find how many sets there are in the set
  5. The minimum number of operations isNumber of sets minus 1

The problem solving code

var makeConnected = function(n, connections) {
    // Check whether the number of cables is sufficient
    if (connections.length < n - 1) return -1
    
    // Define and look up the set
    const unionSet = new UnionSet(n)
    for (const connection of connections) {
        // Connect the computer according to the connection in connections
        unionSet.merge(connection[0], connection[1])}let num = 0
    for (let i = 0; i < n; i++) {
        // Count the number of sets in the set
        if (unionSet.get(i) === i) num++
    }
    
    // Minimum number of operations = set number - 1
    return num - 1
};

/ / 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