Package g1301_1400.s1319_number_of_operations_to_make_network_connected

Class Solution

java.lang.Object

g1301_1400.s1319_number_of_operations_to_make_network_connected.Solution

public class Solution
extends Object

1319 - Number of Operations to Make Network Connected.<p>Medium</p> <p>There are <code>n</code> computers numbered from <code>0</code> to <code>n - 1</code> connected by ethernet cables <code>connections</code> forming a network where <code>connections[i] = [a_i, b_i]</code> represents a connection between computers <code>a_i</code> and <code>b_i</code>. Any computer can reach any other computer directly or indirectly through the network.</p> <p>You are given an initial computer network <code>connections</code>. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.</p> <p>Return <em>the minimum number of times you need to do this in order to make all the computers connected</em>. If it is not possible, return <code>-1</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png" alt="" /></p> <p><strong>Input:</strong> n = 4, connections = [[0,1],[0,2],[1,2]]</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> Remove cable between computer 1 and 2 and place between computers 1 and 3.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png" alt="" /></p> <p><strong>Input:</strong> n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]</p> <p><strong>Output:</strong> 2</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]</p> <p><strong>Output:</strong> -1</p> <p><strong>Explanation:</strong> There are not enough cables.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 10⁵</code></li> <li><code>1 <= connections.length <= min(n * (n - 1) / 2, 10⁵)</code></li> <li><code>connections[i].length == 2</code></li> <li><code>0 <= a_i, b_i < n</code></li> <li><code>a_i != b_i</code></li> <li>There are no repeated connections.</li> <li>No two computers are connected by more than one cable.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	makeConnected(int totalNumberOfComputers, int[][] connections)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

makeConnected

public int makeConnected(int totalNumberOfComputers,
 int[][] connections)