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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int dfs(int node, int** adjList, int* adjSize, bool* restricted, bool* visited) {
6 if (restricted[node] || visited[node]) return 0;
7 visited[node] = true;
8 int count = 1;
9 for (int i = 0; i < adjSize[node]; i++) {
10 count += dfs(adjList[node][i], adjList, adjSize, restricted, visited);
11 }
12 return count;
13}
14
15int reachableNodes(int n, int** edges, int edgesSize, int* edgesColSize, int* restricted, int restrictedSize) {
16 int** adjList = (int**)malloc(n * sizeof(int*));
17 int* adjSize = (int*)malloc(n * sizeof(int));
18 bool* restrictedSet = (bool*)calloc(n, sizeof(bool));
19 bool* visited = (bool*)calloc(n, sizeof(bool));
20 for (int i = 0; i < n; i++) {
21 adjList[i] = (int*)malloc(n * sizeof(int));
22 adjSize[i] = 0;
23 }
24
25 for (int i = 0; i < restrictedSize; i++) {
26 restrictedSet[restricted[i]] = true;
27 }
28
29 for (int i = 0; i < edgesSize; i++) {
30 int a = edges[i][0];
31 int b = edges[i][1];
32 adjList[a][adjSize[a]++] = b;
33 adjList[b][adjSize[b]++] = a;
34 }
35
36 int result = dfs(0, adjList, adjSize, restrictedSet, visited);
37
38 for (int i = 0; i < n; i++) {
39 free(adjList[i]);
40 }
41 free(adjList);
42 free(adjSize);
43 free(restrictedSet);
44 free(visited);
45
46 return result;
47}This approach builds an adjacency list from the input edges, then performs a DFS starting from node 0. It skips over restricted nodes and ensures each node is visited only once. The count of nodes reached is returned as the answer.
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
JavaScript's implementation uses an array as a queue to perform BFS. The method starts at node 0 and progresses level by level, skipping over restricted nodes and tracking visited nodes.