Easy Explaination | Kid of 5 can understand | Penalty and DSUs
🚍 A Tale of Shared Roads: Alice, Bob, and the Government Bus 🚦Imagine a bustling city where Alice and Bob each have their own vehicles to commute. Alice prefers
# \uD83D\uDE8D A Tale of Shared Roads: Alice, Bob, and the Government Bus \uD83D\uDEA6\n\nImagine a bustling city where Alice and Bob each have their own vehicles to commute. Alice prefers her routes, and Bob has his own. However, the government steps in with a unique initiative: free buses that run on shared paths for everyone to use. This initiative sparks a challenge: \n\n**How can we maximize the utilization of shared paths while keeping both Alice and Bob connected across the city?** \uD83E\uDD14\n\nLet\u2019s solve this intriguing problem together! \uD83D\uDEE0\uFE0F\n\n---\n\n## \uD83D\uDCA1 Intuition\n\nThe idea revolves around understanding **shared resources** (like the government bus routes) versus **exclusive resources** (paths only Alice or Bob can use). Shared paths are prioritized because they reduce redundancy and ensure efficient connectivity for both Alice and Bob. (Atleast that\'s how i got intuition like AMTS/BRTS(if you know you know\uD83E\uDD23\uD83D\uDE02) are cheaper than private vehicle petrol and other cost however sometimes you have to use no choice )\n\nHere\u2019s the plan:\n- **Shared paths (Type 3):** These are "free" in the sense that both Alice and Bob benefit, so we give them the highest priority (penalty = 0). \uD83D\uDE8C\n- **Exclusive paths (Type 1 or 2):** These come with a penalty (penalty = 1), as only Alice or Bob can use them. \uD83D\uDE97\uD83D\uDE99\n\nBy minimizing the number of redundant paths while keeping both Alice and Bob connected, we ensure an optimal solution. \uD83C\uDFAF\n\n---\n\n## \uD83D\uDEE0\uFE0F Approach\n\n### 1\uFE0F\u20E3 **Penalty-Based Sorting**  \n- Assign a penalty to edges based on their type:\n  - Shared paths (Type 3) are prioritized since they connect both Alice and Bob simultaneously (penalty = 0).  \n  - Exclusive paths (Type 1 or 2) come next (penalty = 1).  \n- Sort the edges by penalty so shared paths are processed first.\n\n### 2\uFE0F\u20E3 **Union-Find (Disjoint Set Union)**  \n- Use the **Union-Find** (or DSU) data structure to manage connectivity.  \n- Maintain two separate DSUs:\n  - One for Alice\'s network (Type 1 + Type 3 paths).  \n  - One for Bob\'s network (Type 2 + Type 3 paths).  \n- Process each edge:\n  - If the edge connects previously unconnected nodes, add it to the respective DSU.  \n  - If the edge is redundant, count it as "removable."  \n\n### 3\uFE0F\u20E3 **Validation**  \n- After processing all edges, check if both Alice and Bob are fully connected (i.e., they each have a single connected component).  \n- If not, return `-1` (it\'s impossible to connect them fully). Otherwise, return the count of redundant edges.\n\n---\n\n## \u23F3 Complexity\n\n- **Time Complexity:**  \n  - Sorting the edges takes $$O(E \\log E)$$, where $$E$$ is the number of edges.  \n  - Union-Find operations are nearly constant time due to path compression, making the overall complexity approximately **$$O(E \\log E)$$**. \u2705\n\n- **Space Complexity:**  \n  - We store parent and size arrays for DSUs, requiring $$O(N)$$ space, where $$N$$ is the number of nodes.  \n\n---\n\n## \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n\nHere\u2019s the full implementation in C++:  \n\n```cpp\nclass DJ {\nprivate:\n    vector<int> parent, gSize;\n\npublic:\n    DJ(int cap) {\n        for (int i = 0; i < cap + 1; i++) {\n            parent.push_back(i);\n            gSize.push_back(1);\n        }\n    }\n\n    bool unionBySize(int node1, int node2) {\n        int ultP1 = getUltPar(node1), ultP2 = getUltPar(node2);\n        if (ultP1 == ultP2) {\n            return false;\n        }\n\n        if (gSize[ultP1] > gSize[ultP2]) {\n            parent[ultP2] = ultP1;\n            gSize[ultP1] += gSize[ultP2];\n        } else {\n            parent[ultP1] = ultP2;\n            gSize[ultP2] += gSize[ultP1];\n        }\n\n        return true;\n    }\n\n    int getUltPar(int node) {\n        if (parent[node] == node)\n            return node;\n        return parent[node] = getUltPar(parent[node]);\n    }\n\n    bool IsSingleComponent() {\n        int ultP = getUltPar(1);\n        for (int i = 1; i < parent.size(); i++) {\n            if (getUltPar(i) != ultP) {\n                return false;\n            }\n        }\n        return true;\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        int aliceSum = 0, bobSum = 0;\n        for (auto& edge : edges) {\n            if (edge[0] != 3)\n                edge.push_back(1);\n            else\n                edge.push_back(0);\n        }\n\n        sort(edges.begin(), edges.end(), [&](vector<int>& a, vector<int>& b) {\n            return a.back() < b.back();\n        });\n\n        DJ alice(n), bob(n);\n\n        int count = 0;\n\n        for (auto& edge : edges) {\n            int from = edge[1], to = edge[2];\n            bool used = false;\n\n            if ((alice.getUltPar(from) != alice.getUltPar(to)) &&\n                (edge[0] == 1 || edge[0] == 3)) {\n                alice.unionBySize(from, to);\n                used = true;\n            }\n\n            if ((bob.getUltPar(from) != bob.getUltPar(to)) &&\n                (edge[0] == 2 || edge[0] == 3)) {\n                bob.unionBySize(from, to);\n                used = true;\n            }\n\n            if (!used) {\n                count++;\n            }\n        }\n\n        if (!alice.IsSingleComponent() || !bob.IsSingleComponent())\n            return -1;\n        return count;\n    }\n};\n\n\n```\n# \uD83D\uDE80 Closing Thoughts\nThis problem is a great analogy for real-world optimization challenges, like city planning or resource allocation. By prioritizing shared resources (the government bus \uD83D\uDE8D) over costly private options (Alice\'s and Bob\'s vehicles \uD83D\uDE97\uD83D\uDE99), we ensure an efficient and cost-effective solution.\n\n\uD83D\uDCAC Did you enjoy this explanation? Let me know your thoughts, suggestions, or any alternate approaches in the comments below! \uD83D\uDC47\n\n\n![image](https://media.tenor.com/xPOkmiPmDT8AAAAM/bhagam-bhag-akshay-kumar-naughty.gif)\n\n# ***If you liked it a upvote will be high appreciated!***
['C++']