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

prompt

  • 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.

Analysis of the

Connectivity problems can be solved with a look-up set. Example 1 of this problem indicates that there are four computers 0,1,2, and 3. Now they are connected to each other by 02,12, and there is one redundant line, and then there is another line left. Therefore, it is only necessary to give the redundant line to the last node.

That we can analyze the first traversal connections, find out the number of redundant line, check traversal and set, find out the number of computers that are not connected (find all nodes of the parent node is equal to the node itself, they are all single collection, remove a large collection, other is the remaining number of computer), determine if it is redundant line can be connected to computers.

code


/ * * *@param {number} n
 * @param {number[][]} connections
 * @return {number}* /
var makeConnected = function (n, connections) {
    const set = new UnionSet(n);
    
    // Find the number of redundant lines
    let over = 0;
    for (let i = 0; i < connections.length; i++) {
        const a = connections[i][0];
        const b = connections[i][1];
        if(set.find(a) ! == set.find(b)) { set.merge(a, b) }else {
            over += 1}}// Find all root nodes
    let root = 0;
    for (let i = 0; i < n; i++) {
        if (set.find(i) === i) root++;
    }
    
    // Check whether the redundant cable is enough for the remaining computer connection
    if (root - 1 > over) {
        return -1
    } else {
        return root - 1}};/** * and look up the set code */
var UnionSet = function (n) {
    this.fathers = new Array(n);
    this.size = new Array(n)
    for (let i = 0; i < n; i++) {
        this.fathers[i] = i
        this.size[i] = 1
    }

}

UnionSet.prototype.find = function (x) {
    if (this.fathers[x] === x) return x;
    return this.find(this.fathers[x])
}

UnionSet.prototype.merge = function (a, b) {
    const fa = this.find(a), fb = this.find(b);
    if (fa === fb) return;
    if (this.size[fa] < this.size[fb]) {
        this.fathers[fa] = fb
        this.size[fb] += this.size[fa]
    } else {
        this.fathers[fb] = fa
        this.size[fa] += this.size[fb]
    }
}


Copy the code