[B] [C] [D]

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.

Their thinking

If the number of network cables is less than the number of computers -1, then all computers cannot be connected to a network, return -1. Otherwise, each computer sees a set, iterates through the input array, joins the two computers, and merges the two computers into one set. Finally get the number of sets, set number -1, is the number of computers that are not connected, that is, the minimum number of operations (because every computer that is not connected needs to be connected, that is, operation once). This kind of problem involving set maintenance can be solved by using and looking up sets. 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]); This.list [x] = root; // Mount the current node as the root node. 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; this.size[rootB] += this.size[rootA] } } } var makeConnected = function(n, Const len = connections.length; const len = connections.length; If (len<n-1) return-1; if(len<n-1) return-1; Const unionset = new unionset (n); For (let I = 0; i<len; // merge(connections[I][0],connections[I][1])} // Merge (connections[I][0],connections[I][1]) const set = new set (); for(let i = 0; i<n; I ++){set.add(unionset. Find (I))} return set.size-1; };Copy the code

At this point we have completed the number of leetcode-1319- connected network operations

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