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.
1import java.util.
In this solution, the adjacency list representation allows for easy traversal of nodes. The DFS method visits nodes to form paths and checks conditions for being a good path when visiting from node to node.