aboutsummaryrefslogtreecommitdiff
path: root/num_op_connect_network.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'num_op_connect_network.cpp')
-rw-r--r--num_op_connect_network.cpp41
1 files changed, 41 insertions, 0 deletions
diff --git a/num_op_connect_network.cpp b/num_op_connect_network.cpp
new file mode 100644
index 0000000..a519f66
--- /dev/null
+++ b/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(int) & connections) {
+ if (connections.size() < n - 1)
+ return -1;
+ vvd(int) 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(int) & 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(int) c1 = {{0, 1}, {0, 2}, {1, 2}};
+ vvd(int) c2 = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}};
+ vvd(int) 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));
+}