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.