C++ O(N) Union with Rank and Find with Path Compression with clear comments in code.
First, lets talk about why we need to do this with Union-Find  in the context of an interview ? \nUnion Find is required for  follow-ups like what if the graph 
First, lets talk about why we need to do this with Union-Find  in the context of an interview ? \nUnion Find is required for  **follow-ups** like what if the graph is large (cant use DFS) , OR what if the components (edge connections) dynamically change etc ? . \n\nI believe this question teaches us the basic nitty-gritties of **Union Find (with Rank and Path compression)**. If you do normal UF without Rank and Path compression, then the TC will be the same as DFS or BFS and interviewer will ask you to implement Rank and Path Compression so minimize the TC to O(N). So better to learn it with Rank and Path Compression at the get go !\n\n**PRE_REQUISITE** : [ Disjoint Sets Data Structure - Weighted Union and Collapsing Find](https://www.youtube.com/watch?v=wU6udHRIkcc)\n\n**Once youve understood the video completely above**, my code is fairly readable with comments. \n\n **Time Complexity**    \n \n it is **O(N  alpha(N))**, where **alpha(N**) is called the "*Inverse Ackermann Function*", which is basically a fancy way of saying that **alpha(N) grows VERY SLOWLY** (in practise alpha(N) is <= 4). So, the complexity reduces O( N ), *where N is the number of Nodes in the graph*.   \n \nIntuitively thinking, we can say in an interiview that we make AT MOST N queries to our **Union** Function, so TC is bounded by N queries i.e O(N) . \n\n```\nclass DisjointDS{\npublic:\n  vector<int> parent; // Stores the parent of ith node\n  vector<int> rank; //Stores the rank of ith node\n  \n  DisjointDS(int n){ //n is the number of nodes in the graph\n    parent.resize(n + 1); \n    rank.resize(n + 1);  \n    rank.clear(); //Initialize the rank of every node as 0\n    \n    for(int i = 0; i < n+1; i++){ //Inititalize the parent of node i as i itself. Meaning they are a set on their own\n      parent[i] = i;\n    }\n  }\n  \n  bool Union(int u, int v){ //Union by Rank . Returns TRUE if UNION can be performed without introducing any cycle\n    //Get the representatives of the vertices\n    int ru = Find(u);\n    int rv = Find(v);\n  \n    //an edge between them will create a loop since they both belong to the same set/component\n    if(ru == rv) return false; \n    \n    if(rank[ru] > rank[rv]){\n      parent[rv] = parent[ru];\n    }else if (rank[rv] > rank[ru]){\n      parent[ru] = parent[rv];\n    }else{\n      parent[rv] = parent[ru];\n      rank[ru]++;\n    }\n    return true;\n  }\n  \n  int Find(int node){ //Returns the representative of this node\n    if(parent[node] == node) return node; //If i am my own parent/rep\n    //Find with Path compression, meaning we update the parent for this node once recursion returns\n    parent[node] = Find(parent[node]); \n    return parent[node];\n  }\n};\n\nclass Solution {\npublic:\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n      int numOfNodes =  edges.size();\n      DisjointDS dds(numOfNodes);\n      \n      for(auto& edge: edges){\n        int u = edge[0];\n        int v = edge[1];\n        \n        if(dds.Union(u, v) == false) return {u, v}; // If we cannot unionize these 2 edges, means they must beling to the same\n        //connected component, hence adding them will create a cycle. so we found our Redundant Edge\n      }\n      \n      return {-1, -1};\n    }\n};\n```\n
['Union Find', 'C', 'C++']