题目描述

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(并查集)

首先判断线缆的个数是否能将网络连通。如果线缆的个数小于结点个数-1，则表示网络无法连通，return -1;
如果网络可以连通，那么将连通的网络放入同一集合当中。然后集合的个数就是要进行的操作数。

时间复杂度

O(m) m为边的个数

参考文献

C++ 代码

const int N = 100010;
int p[N];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        int m = connections.size();
        int cnt = n;
        if(m < n - 1) return -1;
        for(int i = 0; i<n; i++) p[i] = i;
        for(auto edge : connections){
            int a = edge[0], b = edge[1];
            a = find(a), b = find(b);
            if(a == b) continue;
            else{
                p[a] = b;
                cnt--;
            }
        }
        return cnt - 1;
    }
};

算法3（DFS）

从上面的算法可以看出来，只要找到连通分量的个数就可以得到答案了，所以用dfs遍历图，找到dfs的个数。
我用了静态链表和压位，刚刚学的，试一试。
调试的时候遇到了一个问题，就是明明执行的时候没有问题，但是提交了就WA，解决办法就是不要用全局变量，在类里面声明变量。

C++代码

class Solution {
public:
    int g[100010], e[100010], ne[100010], idx = 0;
    bitset<100010> st;
    void dfs(int v){
        st[v] = 1;
        for(int i = g[v]; i != -1; i = ne[i]){
            if(!st[e[i]]) dfs(e[i]);
        }
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        if(connections.size() < n - 1) return -1;
        memset(g, -1, sizeof(g));
        for(auto edge : connections){//建立图
            int v = edge[0], w = edge[1];
            e[idx] = w, ne[idx] = g[v], g[v] = idx++;
            e[idx] = v, ne[idx] = g[w], g[w] = idx++; 
        }

        int ans = 0;
        for(int i = 0; i<n; i++){
            if(st[i] == 0){
                ans += 1;
                dfs(i);
            }
        }
        return ans - 1;;
    }
};