Binary search with dfs, easy solution with comments
IntuitionApproachComplexity
Time complexity: O(n*log(n))

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n*log(n))
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    // Depth First Search (DFS) function to count the number of nodes reachable
    // from node 'i'. Parameters:
    // - i: Current node being visited.
    // - maxWeight: Maximum allowed weight for edges to traverse.
    // - graph: Reverse adjacency list representation of the graph.
    // - visited: Vector to keep track of visited nodes.
    int dfs(int i, int maxWeight, vector<vector<pair<int, int>>>& graph,
            vector<int>& visited) {
        // Mark the current node as visited.
        visited[i] = 1;

        // Initialize the count of reachable nodes from the current node.
        int reachableNodes = 1;

        // Traverse all neighbors of the current node.
        for (auto& [neighbor, weight] : graph[i]) {
            // If the edge weight is within the allowed limit and the neighbor
            // is not visited:
            if (weight <= maxWeight && !visited[neighbor]) {
                // Recursively perform DFS on the neighbor and add the result to
                // reachableNodes.
                reachableNodes += dfs(neighbor, maxWeight, graph, visited);
            }
        }

        // Return the total number of reachable nodes from the current node.
        return reachableNodes;
    }

    // Function to find the minimum maximum edge weight such that all nodes are
    // reachable from node 0. Parameters:
    // - n: Total number of nodes in the graph.
    // - edges: List of edges, where each edge is represented as {from, to,
    // weight}. Returns:
    // - The minimum maximum weight if all nodes are reachable, otherwise -1.
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        // Step 1: Build the reverse adjacency list representation of the graph.
        // Each entry in the graph stores a pair {neighbor, weight}.
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            graph[to].emplace_back(from, weight);
        }

        // Step 2: Initialize binary search range for the maximum weight.
        int left = 1;        // Minimum possible weight.
        int right = 1000001; // Maximum possible weight (upper bound).

        // Step 3: Perform binary search to find the smallest maximum weight.
        while (left < right) {
            // Calculate the midpoint of the current range.
            int mid = (left + right) / 2;

            // Create a visited array to track visited nodes during the DFS.
            vector<int> visited(n, 0);

            // Check if all nodes are reachable from node 0 with the current
            // weight limit (mid).
            if (dfs(0, mid, graph, visited) == n) {
                // If all nodes are reachable, try to minimize the maximum
                // weight.
                right = mid;
            } else {
                // If not all nodes are reachable, increase the weight limit.
                left = mid + 1;
            }
        }

        // Step 4: Return the result.
        // If left exceeds the upper bound, it means no valid weight was found.
        return left == 1000001 ? -1 : left;
    }
};
```
['C++']