Sponsored
Sponsored
This approach involves the following steps:
Time Complexity: O(V + E), where V is the number of nodes and E is the number of edges, since we're effectively traversing all nodes and edges.
Space Complexity: O(V + E), due to the storage needed for the graph representation and the ancestors lists.
1#include <vector>
2#include <queue>
3#include <set>
4using namespace std;
5
6vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
7 vector<vector<int>> graph(n);
8 vector<int> indegree(n, 0);
9 vector<set<int>> ancestors(n);
10
11 for (const auto& edge : edges) {
12 graph[edge[0]].push_back(edge[1]);
13 indegree[edge[1]]++;
14 }
15
16 queue<int> zero_indegree;
17 for (int i = 0; i < n; ++i) {
18 if (indegree[i] == 0) {
19 zero_indegree.push(i);
20 }
21 }
22
23 while (!zero_indegree.empty()) {
24 int node = zero_indegree.front();
25 zero_indegree.pop();
26 for (int neighbor : graph[node]) {
27 ancestors[neighbor].insert(node);
28 ancestors[neighbor].insert(ancestors[node].begin(), ancestors[node].end());
29 if (--indegree[neighbor] == 0) {
30 zero_indegree.push(neighbor);
31 }
32 }
33 }
34
35 vector<vector<int>> result(n);
36 for (int i = 0; i < n; ++i) {
37 result[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());
38 }
39 return result;
40}
41
42// Example usage
43// int main() {
44// int n = 8;
45// vector<vector<int>> edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
46// vector<vector<int>> result = getAncestors(n, edges);
47// // Output result
48// }In this C++ solution, we utilise a queue for nodes with zero indegree to ensure nodes are processed in topological order. This is achieved by reducing the indegree for each of its neighbors and collecting ancestors for each node. The ancestors are maintained in sets, enabling simple merging and ensuring automatic sorting when converted to a vector.
Here, we reverse the edges in the graph and then perform a DFS for each node to find all reachable nodes, which now represent ancestors. This is an implementation that directly finds ancestors by traversing upwards in the graph via reversed edges:
Time Complexity: O(V * (V + E)), due to performing DFS from every node and having potential to traverse the full graph per DFS call.
Space Complexity: O(V + E), where V storage comes from graph information and visited nodes tracking.
1from collections import
This solution reverses the direction of edges and applies DFS for each node to find reachable nodes (representing ancestors). Each DFS invocation tracks visited nodes to prevent reprocessing and adds ancestors directly to the current node's list, which is then sorted for output.