Number of Possible Sets of Closing Branches

Shortest Path

Original Link

Solution

In the problem, we should find all possible ways to close the branches. All the branches that survive must be connected to each other, and the distance between them should be no longer than the maximum distance.

The maximum input of n is 10, so there are only 1024 states to select the survived branches. Also, we should find all the shortest paths from each branch to the others. It will take N*NlogN times to detect whether the current state is valid. So, it will be O(2^N * N^2logN). This value is really low even with N = 10.

• Iterates all possible ways to select the survived branches.

• Iterates all survived branches as the starting branch to find the shortest path to other branches.

• Check if there is any case that one branch cannot connect to the other branch. If there is any, then this cannot be possible.

#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        unordered_map<int, vector<pair<int, int>>> graph;

        // Build adjacency list representation of the graph
        for (const auto& road : roads) {
            int u = road[0], v = road[1], w = road[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }

        int validSets = 1; // At least one valid set (empty set)
        
        // Iterate over all subsets of branches (bitmasking)
        for (int mask = 1; mask < (1 << n); ++mask) {
            vector<int> openBranches;

            // Extract the branches that are open in this subset
            for (int j = 0; j < n; ++j) {
                if (mask & (1 << j)) { // Check if branch `j` is included
                    openBranches.push_back(j);
                }
            }

            bool isValid = true;

            // Run Dijkstra's algorithm for each branch in the subset
            for (auto& startNode : openBranches) {
                vector<int> dist(n, -1); // Distance array initialized to -1
                dist[startNode] = 0;

                priority_queue<pair<int, int>> pq;
                pq.push({0, startNode}); // {distance, node}

                while (!pq.empty()) {
                    auto [negDistance, node] = pq.top();
                    pq.pop();
                    int currDistance = -negDistance; // Convert back to positive distance

                    // If this path is not optimal, skip
                    if (dist[node] != -1 && dist[node] < currDistance) continue;

                    // Relax edges
                    for (auto& [neighbor, weight] : graph[node]) {
                        if (mask & (1 << neighbor)) { // Only consider nodes in the subset
                            int newDistance = currDistance + weight;
                            if ((dist[neighbor] == -1 || dist[neighbor] > newDistance) && newDistance <= maxDistance) {
                                dist[neighbor] = newDistance;
                                pq.push({-newDistance, neighbor}); // Push with negative distance for min-heap
                            }
                        }
                    }
                }

                // Check if all selected branches are reachable
                for (auto& branch : openBranches) {
                    if (dist[branch] == -1) {
                        isValid = false;
                        break;
                    }
                }

                if (!isValid) break;
            }

            if (isValid) validSets++; // Count this subset if it's valid
        }

        return validSets;
    }
};

Time Complexity Analysis

• Generating subsets: O(2^n) (Iterating over all subsets)

• Dijkstra's Algorithm: O(nlog⁡n) per subset (Priority queue operations)

• Checking All Subsets: O(n) in worst case

Thus, the overall complexity is O(2^n⋅n^2⋅log n), making this approach feasible only for small n (typically n≤20).