Minimum Score of a Path Between Two Cities

class DisjointSet {
private:
    vector<int> link, size;
    
public:
    DisjointSet(int capacity) {
        link.resize(capacity);
        size.resize(capacity, 0);
        for (int i = 0; i < capacity; i++) {
            link[i] = i;
        }
    }
    int find(int p) {
        if (link[p] != p) link[p] = find(link[p]);
        return link[p];
    }
    void merge(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return;
        if (size[rootA] < size[rootB]) {
            link[rootA] = rootB;
        } else if (size[rootA] > size[rootB]) {
            link[rootB] = rootA;
        } else {
            link[rootB] = rootA;
            size[rootA]++;
        }
    }
};
    
class Algorithms {
public:
    int minimumScore(int n, vector<vector<int>>& connections) {
        DisjointSet dsu(n + 1);
        int minScore = numeric_limits<int>::max();
    
        for (auto& conn : connections) {
            dsu.merge(conn[0], conn[1]);
        }
    
        for (auto& conn : connections) {
            if (dsu.find(1) == dsu.find(conn[0])) {
                minScore = min(minScore, conn[2]);
            }
        }
    
        return minScore;
    }
};

This C++ program finds the minimum score of any path between two cities using a graph represented by city connections. Each city connection consists of an array where the first two elements are the cities connected and the third element is the score (cost) of this connection.

The solution uses a Disjoint Set Union (DSU) data structure to efficiently manage and merge the sets of connected cities, ensuring that connected components can be easily identified and manipulated with operations like find and merge.

The DisjointSet class provides the basic functionality for the DSU:

• Initialization: Creates a link array where each index points to itself and an initial size of zero for each component.
• Find Operation: Uses path compression for efficiency, ensuring that the nodes directly point to the representative node after finding the root.
• Union by Size: Combines two sets by size, linking the smaller tree under the larger one to keep the tree as flat as possible.

The Algorithms class contains the minimumScore function which calculates the minimum score from the city labeled 1 to any other city:

1. Initialize a DSU instance to accommodate n cities.
2. Merge cities based on given connections.
3. Check each connection, and if it connects back to the city 1 (indicating a possible path from 1), update the minimum score if the current connection's score is smaller than the previously recorded minimum score.

The path score considered here is the connection score directly between two cities, not accounting for aggregate scores across multiple segments of a path. This simplifies the problem to the direct connections available from city 1. The DSU helps in quickly determining the components connected directly or indirectly to city 1, ensuring efficient computation of the desired minimum score path condition.

class DisjointSet {
    int[] leader;
    int[] depth;
    
    public DisjointSet(int length) {
        leader = new int[length];
        for (int i = 0; i < length; i++)
            leader[i] = i;
        depth = new int[length];
    }
    
    public int find(int member) {
        if (leader[member] != member)
            leader[member] = find(leader[member]);
        return leader[member];
    }
    
    public void merge(int node1, int node2) {
        int leader1 = find(node1), leader2 = find(node2);
        if (leader1 == leader2) {
            return;
        } else if (depth[leader1] < depth[leader2]) {
            leader[leader1] = leader2;
        } else if (depth[leader1] > depth[leader2]) {
            leader[leader2] = leader1;
        } else {
            leader[leader2] = leader1;
            depth[leader1]++;
        }
    }
}
    
class MinimumScoreSolution {
    public int calculateMinimumScore(int nodes, int[][] connectivity) {
        DisjointSet disjointSet = new DisjointSet(nodes + 1);
        int minimalScore = Integer.MAX_VALUE;
    
        for (int[] connection : connectivity) {
            disjointSet.merge(connection[0], connection[1]);
        }
    
        for (int[] connection : connectivity) {
            if (disjointSet.find(1) == disjointSet.find(connection[0])) {
                minimalScore = Math.min(minimalScore, connection[2]);
            }
        }
    
        return minimalScore;
    }
}

The provided Java solution is designed to find the minimum score of a path between two cities using a graph-like model represented by nodes and connections. The principal structures used are:

• DisjointSet class - This class is utilized to manage the disjoint sets of nodes. It has two main operations:
  • find operation to determine the root of a set,
  • merge operation that unites two subsets.
• MinimumScoreSolution class - This class contains the method calculateMinimumScore which leverages the Disjoint Set to compute the minimal score path between two nodes.

Here's how the solution operates:

1. Initialize a DisjointSet instance with nodes. The constructor of DisjointSet initializes each node to be its own leader and sets a uniform depth of all nodes.
2. Iterate through the given connectivity pairs (edges), merging nodes together. This step essentially builds the union of the graph where direct connectivity between nodes is considered.
3. Iterate again through the connectivity pairs and use the find method from the DisjointSet instance to check if there exists a connection to the node in interest (node 1 in this case). If there's a path from node '1' to any selected connection, compute the minimal score by comparing path scores.
4. Return the computed minimal score.

This solution employs the union-find algorithm to efficiently union and find sets of nodes and uses it to enforce a direct or indirect connection between cities to ascertain the minimum score path. Notably, the correctness of this approach assumes that the input connectivity array gives a connected graph where each element also provides a score (implied but not directly observable in the provided code).