# 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] = [ai, bi]` represents a connection between computers `ai` and `bi`. Any computer can reach any other computer directly or indirectly through the network.

You are 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 is not possible, return `-1`.

Example 1:

``````Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: 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: -1
Explanation: There are not enough cables.
``````

Constraints:

• `1 <= n <= 105`
• `1 <= connections.length <= min(n * (n - 1) / 2, 105)`
• `connections[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• There are no repeated connections.
• No two computers are connected by more than one cable.

``````class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
int cnt = 0;
vector<vector<int>> g(n);
vector<bool> visited(n);
for (auto &c : connections) {
g[c[0]].push_back(c[1]);
g[c[1]].push_back(c[0]);
}
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
++cnt;
dfs(g, i, visited);
}
return cnt - 1;
}
void dfs(vector<vector<int>>& g, int i, vector<bool>& visited) {
visited[i] = true;
for (int next : g[i]) {
if (visited[next]) continue;
dfs(g, next, visited);
}
}
};
``````

``````class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
int cnt = n;
vector<int> root(n);
for (int i = 0; i < n; ++i) root[i] = i;
for (auto &c : connections) {
int x = getRoot(root, c[0]), y = getRoot(root, c[1]);
if (x != y) {
--cnt;
root[x] = y;
}
}
return cnt - 1;
}
int getRoot(vector<int>& root, int i) {
return (root[i] == i) ? i : (root[i] = getRoot(root, root[i]));
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1319

Number of Islands

https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/

https://leetcode.com/problems/number-of-operations-to-make-network-connected/solutions/717403/c-dfs-number-of-islands-detailed-explanation/

https://leetcode.com/problems/number-of-operations-to-make-network-connected/solutions/477660/java-count-number-of-connected-components-clean-code/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation