Leetcode 2368: Reachable Nodes With Restrictions
You are given a tree with n nodes and n - 1 edges, where nodes are labeled from 0 to n - 1. Additionally, a list of restricted nodes is provided. Your goal is to determine the maximum number of nodes that can be visited starting from node 0, without passing through any restricted node. Node 0 itself is not restricted.
Problem
Approach
Steps
Complexity
Input: You are given the number of nodes n, a list of edges describing the tree, and a list of restricted nodes.
Example: n = 6, edges = [[0,1], [0,2], [2,3], [3,4], [4,5]], restricted = [2, 5]
Constraints:
• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges represents a valid tree
• 1 <= restricted.length < n
• 1 <= restricted[i] < n
• All restricted nodes are unique
Output: Return the maximum number of nodes that can be reached from node 0 without passing through any restricted node.
Example: Output: 3
Constraints:
Goal: The goal is to find the maximum reachable nodes starting from node 0 while avoiding restricted nodes.
Steps:
• Construct an adjacency list from the given edges.
• Mark all restricted nodes as visited.
• Perform a Depth First Search (DFS) or Breadth First Search (BFS) starting from node 0, skipping any restricted nodes.
• Count the number of nodes visited during the traversal.
Goal: The tree structure guarantees a valid configuration of nodes and edges. The restricted nodes list contains unique values, and node 0 is not restricted.
Steps:
• n is between 2 and 10^5
• edges form a valid tree
• restricted nodes are unique and non-empty
Assumptions:
• Node 0 will not be restricted.
• The given tree is valid, and each node can only have a unique set of neighbors.
• Input: Input: n = 6, edges = [[0,1], [0,2], [2,3], [3,4], [4,5]], restricted = [2, 5]
• Explanation: In this example, the nodes that can be visited from node 0 are 1, 3, and 4. Node 2 and node 5 are restricted, so they cannot be visited. Hence, the output is 3.
Approach: To solve this problem, we can use DFS or BFS to traverse the tree from node 0, skipping the restricted nodes and counting how many nodes are reachable.
Observations:
• We need to traverse the tree while avoiding restricted nodes.
• The tree structure ensures no cycles, so DFS/BFS will suffice for traversal.
• This is a graph traversal problem where we need to avoid certain nodes while counting the reachable ones.
Steps:
• 1. Create an adjacency list from the given edges.
• 2. Initialize a visited array to mark restricted nodes and already visited nodes.
• 3. Start DFS or BFS from node 0, avoiding restricted nodes and marking nodes as visited during traversal.
• 4. Count the total number of reachable nodes.
Empty Inputs:
• There will always be at least 2 nodes, so empty inputs are not possible.
Large Inputs:
• For very large inputs (n up to 10^5), the solution should be efficient, ideally O(n) time complexity.
Special Values:
• If there is a large number of restricted nodes, the number of reachable nodes might be significantly reduced.
Constraints:
• Make sure the solution handles the upper limits of constraints effectively.
class Solution {
int ans;
public:
void solve(vector<vector<int>>& gph, vector<bool> &vis, int i) {
vis[i] = true;
for(int n: gph[i]) {
if(!vis[n]) {
ans++;
vis[n] = true;
solve(gph, vis, n);
}
}
}
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
ans = 1;
vector<vector<int>> gph(n);
for(auto e: edges) {
int u = e[0], v = e[1];
gph[u].push_back(v);
gph[v].push_back(u);
}
vector<bool> vis(n, false);
for(auto i: restricted) vis[i] = true;
solve(gph, vis, 0);
return ans;
}
1 : Class Definition
class Solution {
Defines the Solution class that encapsulates the logic for the problem.
2 : Variable Declaration
int ans;
Declares an integer variable 'ans' to keep track of the count of reachable nodes.
3 : Access Modifier
public:
Indicates the start of the public section where the function definitions are located.
4 : DFS Function Definition
void solve(vector<vector<int>>& gph, vector<bool> &vis, int i) {
Defines the 'solve' function which performs a depth-first search (DFS) to explore the graph.
5 : Mark Current Node as Visited
vis[i] = true;
Marks the current node 'i' as visited to prevent revisiting it.
6 : Iterate Over Neighbors
for(int n: gph[i]) {
Iterates over all the neighboring nodes of the current node 'i'.
7 : Check for Unvisited Neighbors
if(!vis[n]) {
Checks if the neighboring node 'n' has not been visited yet.
8 : Increment Reachable Node Count
ans++;
Increments the count of reachable nodes if the neighboring node is valid.
9 : Mark Neighbor as Visited
vis[n] = true;
Marks the neighboring node 'n' as visited.
10 : Recursive DFS Call
solve(gph, vis, n);
Recursively calls the 'solve' function for the unvisited neighbor 'n'.
11 : Main Function Definition
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
Defines the 'reachableNodes' function which is the main function that calculates the number of reachable nodes.
12 : Initialize Answer
ans = 1;
Initializes 'ans' to 1, counting the starting node (node 0) as reachable.
13 : Graph Initialization
vector<vector<int>> gph(n);
Initializes an adjacency list 'gph' to represent the graph with 'n' nodes.
14 : Build Graph
for(auto e: edges) {
Iterates over the edges and builds the undirected graph by adding each edge to the adjacency list.
15 : Edge Processing
int u = e[0], v = e[1];
Extracts the nodes 'u' and 'v' from the current edge 'e'.
16 : Add Edge to Graph
gph[u].push_back(v);
Adds node 'v' to the adjacency list of node 'u', creating an undirected edge.
17 : Add Reverse Edge
gph[v].push_back(u);
Adds node 'u' to the adjacency list of node 'v', ensuring the graph is undirected.
18 : Initialize Visited Vector
vector<bool> vis(n, false);
Initializes a boolean vector 'vis' to track which nodes have been visited.
19 : Mark Restricted Nodes
for(auto i: restricted) vis[i] = true;
Marks the restricted nodes as visited in the 'vis' vector.
20 : Start DFS Traversal
solve(gph, vis, 0);
Starts the DFS traversal from node 0, passing the graph and visited vector.
21 : Return Result
return ans;
Returns the count of reachable nodes, which is stored in 'ans'.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Since we traverse all nodes once, the time complexity is O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the adjacency list and visited nodes array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus