class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
// to connect n nodes, we need at least n - 1 edges
if (connections.size() < n - 1)
return -1;
int numOfConnected = 0;
vector<vector<int>> graph(n);
unordered_set<int> seen;
for (const auto& conn : connections) {
graph[conn[0]].push_back(conn[1]);
graph[conn[1]].push_back(conn[0]);
}
for (int i = 0; i < n; ++i)
if (seen.insert(i).second) {
dfs(graph, i, seen);
++numOfConnected;
}
return numOfConnected - 1;
}
private:
void dfs(const vector<vector<int>>& graph, int u, unordered_set<int>& seen) {
for (const int v : graph[u])
if (seen.insert(v).second)
dfs(graph, v, seen);
}
};
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/number-of-operations-to-make-network-connected/
Top comments (0)