minimum-spanning-tree

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3600 - Maximize Spanning Tree Stability with Upgrades

LeetCode Problem 3600 Difficulty: 🔴 Hard Topics: Binary Search, Greedy, Union-Find, Graph Theory, Minimum Spanning Tree Solution Problem Understanding This problem asks us to determine the maximum possible stability of a spanning tree built from a weighted, undirected graph with certain constraints. Each edge in the graph has a strength and a mandatory flag . A mandatory edge ( musti == 1 ) must appear in the spanning tree, and...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1135 - Connecting Cities With Minimum Cost

LeetCode Problem 1135 Difficulty: 🟡 Medium Topics: Union-Find, Graph Theory, Heap (Priority Queue), Minimum Spanning Tree Solution Problem Understanding This problem asks us to connect n cities together using a set of possible bidirectional connections. Each connection has a cost, and our goal is to connect every city while minimizing the total cost. More formally, we are given: An integer n , representing cities labeled from 1 to n A...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1724 - Checking Existence of Edge Length Limited Paths II

LeetCode Problem 1724 Difficulty: 🔴 Hard Topics: Depth-First Search, Union-Find, Graph Theory, Design, Sorting, Heap (Priority Queue), Minimum Spanning Tree Solution LeetCode 1724 - Checking Existence of Edge Length Limited Paths II Problem Understanding This problem gives us an undirected weighted graph with n nodes and a list of edges. Each edge connects two nodes and has an associated distance value. The graph may contain multiple edges between the same...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

LeetCode Problem 1489 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory, Sorting, Minimum Spanning Tree, Strongly Connected Component Solution Problem Understanding The problem gives us a connected, weighted, undirected graph with n vertices and a list of edges. Each edge is represented as [u, v, weight] , meaning there is a bidirectional connection between vertices u and v with the given cost. The goal is not simply to compute one Minimum...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1168 - Optimize Water Distribution in a Village

LeetCode Problem 1168 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory, Heap (Priority Queue), Minimum Spanning Tree Solution Problem Understanding The problem asks us to supply water to all houses in a village in the most cost-effective way. Each house has two options: either build a well in the house with a fixed cost, or connect the house to another house via pipes, where each pipe has its own construction cost....

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1584 - Min Cost to Connect All Points