LeetCode-1319. Number of Operations to Make Network Connected

LeetCode-1319. Number of Operations to Make Network Connected

There are ​​n​​​ computers numbered from ​​0​​​ to ​​n-1​​​ connected by ethernet cables ​​connections​​​ forming a network where ​​connections[i] = [a, b]​​​ represents a connection between computers ​​a​​​ and ​​b​​. Any computer can reach any other computer directly or indirectly through the network.

Given an initial computer network ​​connections​​. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it's not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]Output: 1Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]Output: 2

Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]Output: -1Explanation: There are not enough cables.

Example 4:

Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]Output: 0

Constraints:

​​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 repeated connections.No two computers are connected by more than one cable.

题解：

并查集。

统计连通分量个数和多出的线个数，首先判断能否满足全连接（即多出的线个数不少于连通分量个数-1），然后返回答案。

class Solution {public: void Union(int x, int y, vector &f) { int fx = Find(x, f); int fy = Find(y, f); if (fx != fy) { f[fy] = fx; } } int Find(int x, vector &f) { if (x != f[x]) { return Find(f[x], f); } return x; } int makeConnected(int n, vector>& connections) { int lines = 0, sets = 0; vector f(n, 0); for (int i = 0; i < n; i++) { f[i] = i; } for (int i = 0; i < connections.size(); i++) { if (Find(connections[i][0], f) != Find(connections[i][1], f)) { Union(connections[i][0], connections[i][1], f); } else { lines++; } } for (int i = 0; i < n; i++) { if (f[i] == i) { sets++; } } int res = lines - sets + 1; if (res < 0) { return -1; } return sets - 1; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。