原题链接：Leetcode 1319. 连通网络的操作次数

并查集+路径压缩

class Solution {
public:
    map<int,int> fa;
    int findfather(int x)
    {
        int a=x;
        while(x!=fa[x])  x=fa[x];
        while(a!=fa[a])
        {
            int z=fa[a];
            a=fa[a];
            fa[z]=x;
        }
        return x;
    }
    void Union(int x,int y)
    {
        int fx=findfather(x);
        int fy=findfather(y);
        if(fx!=fy) fa[fx]=fy;

    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        int num=connections.size();
        if(num<n-1) return -1;
        for(int i=0;i<n;i++) fa[i]=i;
        int res=0;
        for(auto x:connections)
        {
            int a=x[0],b=x[1];
            if(findfather(a)!=findfather(b)) 
            {
                Union(a,b);
                res++;
            }
        }
        return n-1-res;
    }
};

class Solution {
public:
    map<int,int> fa;
    set<int> father;
    int findfather(int x)
    {
        int a=x;
        while(x!=fa[x]) x=fa[x];
        while(a!=x)
        {
            int tmp=a;
            a=fa[a];
            fa[tmp]=x;
        }
        return x;
    }
    void Union(int x,int y)
    {
        int fx=findfather(x);
        int fy=findfather(y);
        if(fx!=fy) fa[fy]=fx;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        int num=connections.size();
        if(num<n-1) return -1;
        for(int i=0;i<n;i++) fa[i]=i;
        int res=0;
        for(auto x:connections)
        {
            int a=x[0],b=x[1];
            Union(a,b);
        }
        for(int i=0;i<n;i++) father.insert(findfather(i));
        return father.size()-1;
    }
};

DFS

class Solution {
public:
    vector<int> visited;
    vector<vector<int>> adj;
    void dfs(int i)
    {
        visited[i]=1;
        for(auto x:adj[i])
        {
            if(!visited[x]) dfs(x);
        }
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        int num=connections.size();
        if(num<n-1) return -1;
        adj.resize(n);
        visited.resize(n);
        for(auto x:connections)
        {
            int i=x[0],j=x[1];
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
        int res=0;
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                dfs(i);
                res++;
            }
        }
        return res-1;
    }
};