Leetcode 882. Reachable Nodes In Subdivided Graph
Problem Explanation
In this problem, we are given some initially connected nodes in a graph. The graph is not necessarily a completely connected graph and might have multiple connected components. Then some of these connections are subdivided by adding n
new nodes between every i
and j
. After that, we are supposed to find out how many nodes we can reach starting from node 0 with at most a M
number of moves. A move is defined by travelling along one edge.
The overall problem can be solved by using Dijkstra Algorithm. We apply the Dijkstra Algorithm to mark and record all the nodes that can be reached within M
moves.
Example
Let's consider the example edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4.
Here, we have 4 nodes initially and the direct connections between them are described by the first two indices of each sub array in the edges
input.
- 0 -> 1 and 1 -> 0 with
4
added nodes and an edge between each - 0 -> 2 and 2 -> 0 with
8
added nodes and an edge between each - 1 -> 2 and 2 -> 1 with
6
added nodes and an edge between each - 1 -> 3 and 3 -> 1 with
1
added nodes and an edge between each
Dijkstra Algorithm will count initial nodes reachable within M
moves, meanwhile it will also get the shortest distance from node 0 to each node.
Then we count the reachable nodes on the edge. For each edge, the reachable nodes from one node are min(subnodes, maxMoves - shortestDistanceToTheNode)
. Finally, total reachable nodes is sum of initial nodes and subnodes.
After applying the algorithm, reachable initial nodes are 4, subnodes are 19. Therefore, total reachable nodes are 4 + 19 = 23
, which is the output
.
Python Solution
1 2python 3import collections,heapq 4class Solution: 5 def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int: 6 e = collections.defaultdict(dict) 7 for u,v,n in edges: 8 e[u][v] = e[v][u] = n 9 pq = [(-M, 0)] 10 seen = {0: M} 11 while pq: 12 moves, i = heapq.heappop(pq) 13 moves = -moves 14 for j in e[i]: 15 if moves > e[i][j] and j not in seen or seen[j] < moves - e[i][j] - 1: 16 seen[j] = moves - e[i][j] - 1 17 heapq.heappush(pq, (e[i][j] - moves + 1, j)) 18 ans = len(seen) 19 for u,v,n in edges: 20 ans += min(seen.get(u, 0) + seen.get(v, 0), e[u][v]) 21 return ans
Java Solution
1 2java 3class Solution { 4 public int reachableNodes(int[][] edges, int M, int N) { 5 int[][] graph = new int[N][N]; 6 for (int i = 0; i < N; i++) 7 for (int j = 0; j < N; j++) 8 graph[i][j] = i == j ? 0 : -1; 9 for (int[] edge : edges) { 10 graph[edge[0]][edge[1]] = edge[2]; 11 graph[edge[1]][edge[0]] = edge[2]; 12 } 13 PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> -a[1])); 14 pq.offer(new int[]{0, M}); 15 int res = 0; 16 boolean[] visited = new boolean[N]; 17 int[] maxCount = new int[N]; 18 while (!pq.isEmpty()) { 19 int[] cur = pq.poll(); 20 int start = cur[0]; 21 int move = cur[1]; 22 if (visited[start]) continue; 23 visited[start] = true; 24 res++; 25 for (int i = 0; i < N; i++) { 26 if (graph[start][i] > -1) { 27 if (move > graph[start][i] && !visited[i]) { 28 pq.offer(new int[]{i, move - graph[start][i] - 1}); 29 } 30 graph[i][start] -= Math.min(move, graph[start][i]); 31 maxCount[start] = Math.max(maxCount[start], move); 32 } 33 } 34 } 35 for (int[] edge : edges) { 36 res += Math.min(edge[2], maxCount[edge[0]] + maxCount[edge[1]]); 37 } 38 return res; 39 } 40}
JavaScript Solution
1
2javascript
3var reachableNodes = function(edges, M, N) {
4 let graph = [...Array(N)].map(() => Array(N).fill(-1))
5
6 for (let edge of edges) {
7 let [a, b, dis] = edge
8 graph[a][b] = dis
9 graph[b][a] = dis
10 }
11
12 let visited = Array(N).fill(false)
13 let maxDis = Array(N).fill(-1)
14 maxDis[0] = M
15
16 for (let k = 0; k < N; ++k) {
17 // greedy: select the largest left travel distance node
18 let candidate = -1
19 for (let i = 0; i < N; ++i)
20 if (!visited[i] && (candidate === -1 || maxDis[i] > maxDis[candidate]))
21 candidate = i
22 if (candidate === -1) break
23 visited[candidate] = true;
24 for (let i = 0; i < N; ++i)
25 if (graph[candidate][i] > -1 && maxDis[i] < maxDis[candidate] - graph[candidate][i] - 1)
26 maxDis[i] = maxDis[candidate] - graph[candidate][i] - 1
27 }
28
29 let res = visited.filter(b => b === true).length
30 for (let edge of edges) {
31 let [a, b, dis] = edge
32 res += Math.min(dis, Math.max(0, maxDis[a]) + Math.max(0, maxDis[b]))
33 }
34 return res
35};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int reachableNodes(vector<vector<int>>& edges, int M, int N) { 6 vector<map<int, int>> e(N); 7 for (vector<int> edge: edges) { 8 e[edge[0]][edge[1]] = e[edge[1]][edge[0]] = edge[2]; 9 } 10 priority_queue<pair<int, int>> pq; 11 pq.push({M, 0}); 12 map<int, int> seen; 13 while (pq.size()) { 14 pair<int, int> p = pq.top(); 15 pq.pop(); 16 int moves = p.first, u = p.second; 17 if (!seen.count(u)) { 18 seen[u] = moves; 19 for (auto it: e[u]) { 20 int v = it.first, w = e[u][v]; 21 int moves2 = moves - w - 1; 22 if (!seen.count(v) && moves2 >= 0) { 23 pq.push({moves2, v}); 24 } 25 } 26 } 27 } 28 int ans = seen.size(); 29 for (vector<int> edge: edges) { 30 int u = seen[edge[0]], v = seen[edge[1]], w = edge[2]; 31 ans += min(w, u + v); 32 } 33 return ans; 34 } 35};
C# Solution
1 2csharp 3public class Solution { 4 private Dictionary<int, int> st = new Dictionary<int, int>(); 5 private Dictionary<int, Dictionary<int, int>> g = new Dictionary<int, Dictionary<int, int>>(); 6 7 public int ReachableNodes(int[][] edges, int M, int N) { 8 for (int i = 0; i < N; i++) g[i] = new Dictionary<int, int>(); 9 foreach (var edge in edges) { 10 g[edge[0]][edge[1]] = edge[2] + 1; 11 g[edge[1]][edge[0]] = edge[2] + 1; 12 } 13 14 st[0] = M; 15 while (true) { 16 int x = -1; 17 foreach (var kv in st) { 18 if (kv.Value > 0 && (x == -1 || kv.Value > st[x])) x = kv.Key; 19 } 20 if (x == -1) break; 21 int move = st[x]; 22 st[x] = -1; 23 foreach (var t in g[x]) { 24 int k = t.Key, kk = t.Value; 25 int y = Math.Min(move, kk); 26 st[k] = Math.Max(y + st.GetValueOrDefault(k, -1), st.GetValueOrDefault(k, -1)); 27 g[x][k] -= y; 28 g[k][x] -= y; 29 } 30 } 31 32 int ans = st.Where(kv => kv.Key < N && kv.Value >= 0).Count(); 33 34 foreach (var edge in edges) { 35 ans += Math.Min(edge[2], 36 g[edge[0]].GetValueOrDefault(edge[1], 0) + 37 g[edge[1]].GetValueOrDefault(edge[0], 0)); 38 } 39 40 return ans; 41 } 42}
Although the problem looks complicated at first, it boils down to finding the maximum number of nodes that can be visited using a maximum number of moves in a graph with a special set of rules on how the edges are represented. By representing the graph in a particular way where each edge has a weight equal to the number of steps needed to cross that edge, Dijkstra's algorithm can efficiently find the maximum number of nodes which can be visited with a maximum number of moves starting from node 0.Every language's solution offered above, uses a similar approach. A priority queue is used to keep track of nodes that have not been visited yet. The priority of the node is determined by the number of moves left at that node. The node with maximum moves left is always at the top of the queue. We dequeue from the priority queue, assume the node is visited, and decrease the moves left from every neighbor of the current node. The process is repeated until the priority queue is empty, which indicates all the nodes that could have been visited, have been visited.
While the solutions above vary slightly depending on the language, the basic steps remain the same: represent the graph, use Dijkstraโs algorithm, treat node zero as the start, and keep track of the maximum distance achieved for each node.
The careful implementation of Dijkstraโs algorithm and the representation of the graph are able to handle the specific rules this problem introduces. This includes the unusual idea of nodes between other nodes and the rule that the edges must be used in increasing order.
In conclusion, no matter the programming language used, a firm grasp on the concepts of Dijkstraโs algorithm and graph theory is first needed. With that understanding, the programmer can effectively and efficiently solve such a unique problem as this one, even if it may seem challenging at first glance.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.