aboutsummaryrefslogtreecommitdiff
path: root/num_op_connect_network.cpp
blob: a519f665f1ff89e19302fe7bad164f2ca0e55d1f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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));
}