Sponsored
Sponsored
Performing Depth-First Search (DFS) is a common way to traverse a tree or graph. We'll start from node 0 and explore as far as possible along each branch before backtracking, avoiding restricted nodes and those already visited.
Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4using namespace std;
5
6int dfs(int node, vector<vector<int>>& adjList, unordered_set<int>& restricted, vector<bool>& visited) {
7 if (restricted.count(node) || visited[node])
8 return 0;
9 visited[node] = true;
10 int count = 1;
11 for (int neighbor : adjList[node]) {
12 count += dfs(neighbor, adjList, restricted, visited);
13 }
14 return count;
15}
16
17int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
18 unordered_set<int> restrictedSet(restricted.begin(), restricted.end());
19 vector<vector<int>> adjList(n);
20 for (auto& edge : edges) {
21 adjList[edge[0]].push_back(edge[1]);
22 adjList[edge[1]].push_back(edge[0]);
23 }
24 vector<bool> visited(n, false);
25 return dfs(0, adjList, restrictedSet, visited);
26}This code builds an adjacency list and uses an unordered set for restricted nodes. It utilizes a DFS function to count and return reachable nodes starting from node 0.
Breadth-First Search (BFS) can also be used to traverse the tree level-by-level. Starting from node 0, visit all neighbors at the current depth before moving on to nodes at the next depth level, while skipping restricted nodes.
Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.
1
This BFS approach uses an adjacency list and a queue to explore the tree level-by-level. It checks each neighbor for restrictions and previously visited status before enqueuing it.