LeetCode 1319. Number of Operations to Make Network Connected

Posted on Edited on In 
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
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<vector<int>> g(n);
        for (const auto& c : connections) {
            g[c[0]].push_back(c[1]);
            g[c[1]].push_back(c[0]);
        }
        vector<bool> seen(n, false);
        int cnt = 0;
        function<void(int)> dfs = [&](int cur) {
            for (int next : g[cur])
                if (!seen[next]) {
                    seen[next] = true;
                    dfs(next);
                };
        };
        for (int i = 0; i < n; ++i)
            if (!seen[i]) {
                ++cnt;
                dfs(i);
            }
        return cnt - 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<int> p(n);
        iota(begin(p), end(p), 0);
        function<int(int)> find = [&](int x) {
            return p[x] == x ? x : p[x] = find(p[x]);
        };
        for (const auto& c :connections)
            p[find(c[0])] = find(c[1]);
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (i == p[i])
                ++cnt;
        return cnt - 1;
    }
};