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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int ReachableNodes(int n, int[][] edges, int[] restricted) {
6 var restrictedSet = new HashSet<int>(restricted);
7 var adjList = new Dictionary<int, List<int>>();
8 for (int i = 0; i < n; i++) adjList[i] = new List<int>();
9 foreach (var edge in edges) {
10 adjList[edge[0]].Add(edge[1]);
11 adjList[edge[1]].Add(edge[0]);
12 }
13 return DFS(0, adjList, restrictedSet, new bool[n]);
14 }
15
16 private int DFS(int node, Dictionary<int, List<int>> adjList, HashSet<int> restricted, bool[] visited) {
17 if (restricted.Contains(node) || visited[node])
18 return 0;
19 visited[node] = true;
20 int count = 1;
21 foreach (int neighbor in adjList[node])
22 count += DFS(neighbor, adjList, restricted, visited);
23 return count;
24 }
25}In this C# solution, we use a Dictionary for the adjacency list, and a DFS method which counts nodes starting from node 0, skipping restricted and already visited nodes.
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#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
unordered_set<int> restrictedSet(restricted.begin(), restricted.end());
vector<vector<int>> adjList(n);
for (auto& edge : edges) {
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
queue<int> q;
vector<bool> visited(n, false);
q.push(0);
visited[0] = true;
int count = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
count++;
for (int neighbor : adjList[node]) {
if (!restrictedSet.count(neighbor) && !visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
return count;
}In this C++ solution, BFS is implemented using a queue. Nodes are enqueued if they aren't restricted and haven't been visited, ensuring BFS traversal from node 0.