Sponsored
Sponsored
We can use a union-find (disjoint-set) data structure to solve the problem efficiently. The key idea is to process nodes in order of their values and use the union-find structure to keep track of connected components where nodes can potentially form good paths.
Steps:
Time Complexity: O(E log V + V log V), where E is the number of edges and V is the number of vertices, due to sorting and union-find operations.
Space Complexity: O(V), for storing parent ranks and counts in the union-find structure.
1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5class UnionFind {
6public:
7 UnionFind(int n) : parent(n), rank(n, 1), count(n, 1) {
8 std::iota(parent.begin(), parent.end(), 0);
9 }
10
11 int find(int x) {
12 if (parent[x] != x) {
13 parent[x] = find(parent[x]);
14 }
15 return parent[x];
16 }
17
18 bool unionSets(int x, int y) {
19 int rootX = find(x);
20 int rootY = find(y);
21 if (rootX != rootY) {
22 if (rank[rootX] > rank[rootY]) {
23 parent[rootY] = rootX;
24 count[rootX] += count[rootY];
25 } else if (rank[rootX] < rank[rootY]) {
26 parent[rootX] = rootY;
27 count[rootY] += count[rootX];
28 } else {
29 parent[rootY] = rootX;
30 count[rootX] += count[rootY];
31 rank[rootX]++;
32 }
33 return true;
34 }
35 return false;
36 }
37
38 int size(int x) {
39 return count[find(x)];
40 }
41
42private:
43 std::vector<int> parent;
44 std::vector<int> rank;
45 std::vector<int> count;
46};
47
48int numberOfGoodPaths(std::vector<int>& vals, std::vector<std::vector<int>>& edges) {
49 int n = vals.size();
50 UnionFind uf(n);
51 std::vector<std::vector<int>> neighbors(n);
52 for (const auto& edge : edges) {
53 int u = edge[0], v = edge[1];
54 neighbors[u].push_back(v);
55 neighbors[v].push_back(u);
56 }
57 std::vector<int> nodes(n);
58 std::iota(nodes.begin(), nodes.end(), 0);
59 std::sort(nodes.begin(), nodes.end(), [&vals](int a, int b) {
60 return vals[a] < vals[b];
61 });
62 int result = n;
63 for (int i : nodes) {
64 int current_value = vals[i];
65 int component_size = 0;
66 for (int neighbor : neighbors[i]) {
67 if (vals[neighbor] <= current_value) {
68 uf.unionSets(i, neighbor);
69 }
70 }
71 for (int neighbor : neighbors[i]) {
72 if (vals[neighbor] == current_value) {
73 if (uf.find(neighbor) == uf.find(i)) {
74 component_size += uf.size(neighbor);
75 }
76 }
77 }
78 result += component_size / 2;
79 }
80 return result;
81}We create a UnionFind class with union and find methods to manage components of connected nodes. Nodes are sorted by their values, and for each node, neighbors with equal or lesser values are connected using the union operation. We then count the number of good paths within each component for each value level.
Another way to solve the problem is by using Depth-First Search (DFS) to explore available paths and check if they satisfy the good path conditions. This approach typically involves building the graph from edges and recursively checking paths using DFS while keeping track of the path max value.
Steps:
This approach can become computationally expensive for large graphs but serves as a brute force method to ensure all paths are checked.
Time Complexity: O(V + E) per path exploration, but can be exponential (potentially O(V^2)) if exploring all node pairs for paths.
Space Complexity: O(V), as it uses recursion stack and storage for unique paths.
1function numberOfGoodPaths(vals,
The JavaScript approach uses a similar DFS mechanism as the Java solution, tracking paths and checking the good path criteria while using a set to ensure paths are uniquely recorded as they are calculated.