Sponsored
Sponsored
The nodes that have no incoming edges cannot be reached by any other nodes. Thus, these nodes must be included in the result set for ensuring all nodes in the graph are reachable. This is because they can naturally be start points of paths that reach out to other nodes.
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int* findSmallestSetOfVertices(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize){
6 bool *hasIncoming = (bool*)calloc(n, sizeof(bool));
7 int *result = (int*)malloc(n * sizeof(int));
8 *returnSize = 0;
9
10 for (int i = 0; i < edgesSize; i++) {
11 hasIncoming[edges[i][1]] = true;
12 }
13 for (int i = 0; i < n; i++) {
14 if (!hasIncoming[i]) {
15 result[(*returnSize)++] = i;
16 }
17 }
18 free(hasIncoming);
19 return result;
20}
21We create an array to keep track of nodes with incoming edges. We iterate over all the edges, marking nodes that have incoming edges as true. Finally, we collect all nodes that are not marked as having incoming edges because these are essential to reach all other nodes.