Beats 97% | Easy To Undestand | Disjoint Set 🚀🚀
Intuition\n\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n  - Refere to Disjoint Set video of Apna College for understanding conc
# Intuition\n![Screenshot 2023-10-19 085230.png](https://assets.leetcode.com/users/images/5b12e46e-e133-49aa-bcf4-b412f31a0f3c_1697685792.5509696.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n  - Refere to Disjoint Set video of Apna College for understanding concept of union -- https://youtu.be/C0O8T3C8irU?si=_TpOmuqId3fU8blb\n  - Extraedges are those which are responsible for forming cycle.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int findParent(vector<int>& parent,int node)\n    {\n        if(parent[node] == node) return node;\n\n        return parent[node] = findParent(parent,parent[node]);\n    }\n\n    void unionSet(int u,int v,vector<int>& parent,vector<int>& sz)\n    {\n        u = findParent(parent,u);\n        v = findParent(parent,v);\n\n        if(sz[u] < sz[v])\n        {\n            parent[u] = v;\n            sz[v]++;\n        }\n        else\n        {\n            parent[v] = u;\n            sz[u]++;\n        }\n    }\n\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        \n        vector<int> parent(n);\n        vector<int> sz(n,0);\n\n        for(int i = 0; i < n; i++)\n        {\n            parent[i] = i;\n            sz[i] = 1;\n        }\n\n        int extraEdges = 0;\n        for(auto x : connections)\n        {\n            int u = x[0];\n            int v = x[1];\n\n            u = findParent(parent,u);\n            v = findParent(parent,v);\n\n            if(u == v)\n            {\n                extraEdges++;\n            }\n            else\n            {\n                unionSet(u,v,parent,sz);\n            }\n        }\n\n        int nocc = 0; // number of connected components\n        for(int i = 0; i < n; i++)\n        {\n            if(parent[i] == i) nocc++;\n        }\n\n        int ans = nocc - 1;\n        if(extraEdges >= ans) return ans;\n\n        return -1;\n    }\n};\n```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'C', 'C++', 'Java', 'Python3', 'JavaScript']