C++ | 2 Methods | Easy to Understand
Please upvote if you like the Solution\n\n### Method 1: Using DFS\n\n\nclass Solution {\n\tprivate:\n    void dfs(int source, vector<vector<int>>& edges, vector
**Please upvote if you like the Solution**\n\n### *Method 1: Using DFS*\n\n```\nclass Solution {\n\tprivate:\n    void dfs(int source, vector<vector<int>>& edges, vector<bool>& vis){\n        vis[source] = true;\n        for(auto x:edges[source])\n            if(!vis[x])\n                dfs(x, edges, vis);\n        return;\n    }\n\tpublic:\n    int makeConnected(int n, vector<vector<int>>& conct) {\n        int sz = conct.size();\n        if(sz<n-1)      return -1;\n        vector<bool> vis(n, false);\n        vector<vector<int>> edges(n);\n        for(auto it:conct){ \n            edges[it[0]].push_back(it[1]);\n            edges[it[1]].push_back(it[0]);\n        }\n        int count = 0;\n        for(int i=0;i<n;i++){\n            if(!vis[i]){\n                count++;\n                dfs(i, edges, vis);\n            }\n        }\n        return count-1;\n\t}\n};\n```\n\n### *Method 2: Using Union Find: Best Method*\n```\nclass Solution {\nprivate:\nint findPar(int v, vector<int>& par){\n        if(par[v]==v)   return v;\n        return par[v] = findPar(par[v], par);\n}\npublic:\n    int makeConnected(int n, vector<vector<int>>& conct) {\n\tint sz = conct.size();\n    if(sz<n-1)      return -1;\n\tvector<int> par(n);\n        for(int i=0;i<n;i++)\n            par[i] = i;\n        \n        for(auto it:conct){\n            int a = findPar(it[0], par);\n            int b = findPar(it[1], par);\n            if(a!=b)    par[b] = a;\n        }\n        int count = 0;\n        for(int i=0;i<n;i++)\n            if(par[i]==i)   count++;\n        return count-1;\n    }\n};\n```\n\nPlease Upvote if you like the solution!!!
['Depth-First Search', 'Graph', 'C', 'C++']