Sponsored
Sponsored
This approach involves using the Union-Find data structure (also known as Disjoint Set Union, DSU) to manage connections between cities efficiently. By iterating over all roads, we determine which cities are interconnected. The key is to keep track of the minimum weight of a road that connects these cities after they are all unified.
This solution utilizes an efficient means of finding and unifying elements, reducing the overhead of nested loops and allowing operations near constant-time with path compression and union by rank techniques.
Time Complexity: O(E log* V)
Space Complexity: O(V)
1#include <vector>
2#include <iostream>
3#include <algorithm>
4#include <climits>
5using namespace std;
6
7class UnionFind {
8public:
9 vector<int> parent, rank;
10 UnionFind(int n) {
11 parent.resize(n + 1);
12 rank.resize(n + 1, 0);
13 for(int i = 1; i <= n; i++)
14 parent[i] = i;
15 }
16
17 int find(int u) {
18 if(parent[u] != u)
19 parent[u] = find(parent[u]);
20 return parent[u];
21 }
22
23 void merge(int u, int v) {
24 int pu = find(u);
25 int pv = find(v);
26 if(pu != pv) {
27 if(rank[pu] > rank[pv])
28 parent[pv] = pu;
29 else if(rank[pu] < rank[pv])
30 parent[pu] = pv;
31 else {
32 parent[pv] = pu;
33 rank[pu]++;
34 }
35 }
36 }
37};
38
39int minScore(int n, vector<vector<int>>& roads) {
40 UnionFind uf(n);
41 int minDistance = INT_MAX;
42 for (auto& road : roads) {
43 uf.merge(road[0], road[1]);
44 }
45 int root1 = uf.find(1);
46 for (auto& road : roads) {
47 if (uf.find(road[0]) == root1 || uf.find(road[1]) == root1)
48 minDistance = min(minDistance, road[2]);
49 }
50 return minDistance;
51}
52This solution uses a union-find data structure to first connect all cities. Then, it checks each road to see if it connects to the set containing city 1 and records the minimum distance of these connections.
Another intuitive approach is to use graph traversal techniques such as BFS or DFS. Starting from city 1, you can explore all reachable cities while dynamically updating the minimum edge encountered during the exploration. This ensures you calculate the smallest score path by evaluating all potential paths to the destination city.
Time Complexity: O(V + E)
Space Complexity: O(V + E)
1
This C code uses DFS with an array of lists to store adjacent nodes. During DFS traversal, it keeps track of the minimum-weight edge to ensure the minimum score path is calculated.