1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6void enqueue(int* queue, int* rear, int value) {
7    queue[(*rear)++] = value;
8}
9
10int dequeue(int* queue, int* front) {
11    return queue[(*front)++];
12}
13
14int bfs(int n, int** adjList, int* adjSize, bool* restricted, bool* visited) {
15    int* queue = (int*)malloc(n * sizeof(int));
16    int front = 0, rear = 0;
17    enqueue(queue, &rear, 0);
18    visited[0] = true;
19    int count = 0;
20    while (front != rear) {
21        int node = dequeue(queue, &front);
22        count++;
23        for (int i = 0; i < adjSize[node]; i++) {
24            int neighbor = adjList[node][i];
25            if (!restricted[neighbor] && !visited[neighbor]) {
26                visited[neighbor] = true;
27                enqueue(queue, &rear, neighbor);
28            }
29        }
30    }
31    free(queue);
32    return count;
33}
34
35int reachableNodes(int n, int** edges, int edgesSize, int* edgesColSize, int* restricted, int restrictedSize) {
36    int** adjList = (int**)malloc(n * sizeof(int*));
37    int* adjSize = (int*)malloc(n * sizeof(int));
38    bool* restrictedSet = (bool*)calloc(n, sizeof(bool));
39    bool* visited = (bool*)calloc(n, sizeof(bool));
40    for (int i = 0; i < n; i++) {
41        adjList[i] = (int*)malloc(n * sizeof(int));
42        adjSize[i] = 0;
43    }
44
45    for (int i = 0; i < restrictedSize; i++) {
46        restrictedSet[restricted[i]] = true;
47    }
48
49    for (int i = 0; i < edgesSize; i++) {
50        int a = edges[i][0];
51        int b = edges[i][1];
52        adjList[a][adjSize[a]++] = b;
53        adjList[b][adjSize[b]++] = a;
54    }
55
56    int result = bfs(n, adjList, adjSize, restrictedSet, visited);
57
58    for (int i = 0; i < n; i++) {
59        free(adjList[i]);
60    }
61    free(adjList);
62    free(adjSize);
63    free(restrictedSet);
64    free(visited);
65
66    return result;
67}