LeetCode 2368: Reachable Nodes With Restrictions
Problem Description
Explanation:
To solve this problem, we can perform a Depth First Search (DFS) traversal on the tree starting from node 0 while keeping track of the restricted nodes. We can use a priority queue to prioritize visiting nodes that are not restricted. We will also maintain a set to keep track of visited nodes.
- Initialize a graph data structure to store the edges.
- Perform a DFS traversal starting from node 0 and keep track of the number of nodes visited that are not restricted.
- Use a priority queue to prioritize visiting nodes that are not restricted.
- Maintain a set to keep track of visited nodes and restricted nodes.
- Keep track of the maximum number of nodes visited without visiting a restricted node.
- Return the maximum number of nodes reached from node 0 without visiting a restricted node.
Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(n) for storing the graph and sets. :
Solutions
import java.util.*;
class Solution {
public int reachableNodes(int n, int[][] edges, int[] restricted) {
Map<Integer, List<int[]>> graph = new HashMap<>();
Set<Integer> visited = new HashSet<>();
Set<Integer> restrictedSet = new HashSet<>();
for (int r : restricted) {
restrictedSet.add(r);
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, 1});
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(new int[]{u, 1});
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
pq.offer(new int[]{0, n});
int res = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0];
int moves = curr[1];
if (visited.contains(node)) {
continue;
}
visited.add(node);
if (!restrictedSet.contains(node)) {
res++;
}
if (graph.containsKey(node)) {
for (int[] next : graph.get(node)) {
int nextNode = next[0];
int cost = next[1];
if (!visited.contains(nextNode)) {
int remainingMoves = moves - cost - 1;
if (remainingMoves >= 0) {
pq.offer(new int[]{nextNode, remainingMoves});
}
}
}
}
}
return res;
}
}Loading editor...