[C++] Count Connected Components | Union Find
Logic: We have to count number of connected components and subtract 1 to find number of edges required to connect the graph. \n\nThe code below is optimized ver
**Logic:** We have to count number of connected components and subtract 1 to find number of edges required to connect the graph. \n\nThe code below is optimized version of union find: Union by rank and find with path compression. \n**Time complexity**: ```O(edges*\u03B1(nodes)) \u2248 O(edges)```\n```\nclass DSU{\n    vector<int> rank, parent;\n    public:\n    DSU(int n){\n        rank.resize(n,0);\n        parent.resize(n,0);\n        iota(parent.begin(), parent.end(), 0);\n    }\n    \n    int findParent(int u){\n        if(u == parent[u]) return u;\n        return parent[u] = findParent(parent[u]);\n    }\n    \n    void unionParent(int u, int v){\n        int parU = findParent(u);\n        int parV = findParent(v);\n        \n        if(rank[parU] < rank[parV]){\n            parent[parU] = parV;\n        }\n        else if(rank[parV] < rank[parU]){\n            parent[parV] = parU;\n        }\n        else if(rank[parU] == rank[parV]){\n            parent[parU] = parV;\n            rank[parV] += 1;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        int edges = connections.size();\n        \n        //In order to make graph connected, there should be at least n-1 edges\n        if(edges < n-1) return -1;\n        \n        //Use union find to count number of connected components\n        //No. of operations needed = TotalConnectedComp - 1.\n        \n        int connectedComponent = n;\n        DSU ds(n);\n        for(auto& edge: connections){\n            int u = edge[0], v = edge[1];\n            int parU = ds.findParent(u);\n            int parV = ds.findParent(v);\n            \n            if(parU != parV){\n                ds.unionParent(u, v);\n                connectedComponent -= 1;\n            }\n        }\n\t\tint operationsNeeded = connectedComponent - 1;\n        return operationsNeeded;\n    }\n};\n```
['Union Find', 'C', 'C++']