diff options
Diffstat (limited to 'other/num_op_connect_network.cpp')
-rw-r--r-- | other/num_op_connect_network.cpp | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/other/num_op_connect_network.cpp b/other/num_op_connect_network.cpp new file mode 100644 index 0000000..2a9e2e4 --- /dev/null +++ b/other/num_op_connect_network.cpp @@ -0,0 +1,41 @@ +// 1319. Number of Operations to Make Network Connected +#include "leetcode.h" + +class Solution { +public: + int makeConnected(int n, vvd & connections) { + if (connections.size() < n - 1) + return -1; + vvd adj(n); + for (auto v : connections) { + adj[v[0]].push_back(v[1]); + adj[v[1]].push_back(v[0]); + } + vector<bool> visited(n, false); + int comp = 0; + for (int i = 0; i < n; i++) + if (!visited[i]) { + dfs(adj, visited, i); + comp++; + } + return comp - 1; + } + +private: + void dfs(vvd & adj, vector<bool> &visited, int src) { + visited[src] = true; + for (int i : adj[src]) + if (!visited[i]) + dfs(adj, visited, i); + } +}; + +int main() { + Solution obj; + vvd c1 = {{0, 1}, {0, 2}, {1, 2}}; + vvd c2 = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}}; + vvd c3 = {{0, 1}, {0, 2}, {0, 3}, {1, 2}}; + printf("%d\n", obj.makeConnected(4, c1)); + printf("%d\n", obj.makeConnected(6, c2)); + printf("%d\n", obj.makeConnected(6, c3)); +} |