Find ancestors of each node in the given Graph

By Ann Roberts On Feb 15, 2023

Given a graph in the form of an edge list and a directed graph, return all the ancestors of the nodes in any order. An ancestor is a node one step ahead in the hierarchy on the same path reachable to the current node.

Note: The graph has no cycle.

Examples:

Input: N = 5, Edges[][2] = {{0, 4}, {4, 1}, {4, 3}, {1, 2}}
Output: Result[N][] = {{}, {0, 4}, {0, 1, 4}, {0, 4}, {0}}
Explanation:

Pictorial representation og example 1

As the graph shows the that there are no ancestors to node 0 hence the value of Result[0][] = {} and for the rest of the nodes all the ancestors are given in their respective indices sorted in ascending order.

Input: N = 7, Edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}, {4, 3}, {4, 5}, {6, 3}, {6, 5}}
Output: Result[N][] = {{}, {0}, {0}, {0, 1, 2, 4, 6}, {0, 1, 2}, {0, 1, 2, 4, 6}, {}}

Approach: To solve the problem follow the below idea:

The idea is to store the edges in the adjacency list such that the direction of the edges is reversed. Then perform DFS from all nodes until we exhaust the DFS, and all the nodes visited for a particular node will be its ancestors as all the edges are reversed.

Reverse the edges and store them in the adjacency list adj.
For each node from 0 to n – 1, call DFS and store all the nodes into the vector reached by the DFS.
Store this resultant vector into a 2D vector.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

vector<bool> vis;

void DFS(int u, vector<vector<int> > adj)

{

vis[u] = 1;

for (int v : adj[u]) {

if (vis[v] == 0)

DFS(v, adj);

}

void printResult(vector<vector<int> > res)

{

for (int i = 0; i < res.size(); i++) {

cout << i << " -> ";

for (int j : res[i]) {

cout << j << " ";

}

cout << "\n";

}

void solve(int n, vector<vector<int> > edges)

{

vector<vector<int> > adj(n);

for (int i = 0; i < edges.size(); i++) {

int u = edges[i][0], v = edges[i][1];

adj[v].push_back(u);

}

vector<vector<int> > res(n);

vector<int> arr;

for (int i = 0; i < n; i++) {

vis.assign(n, 0);

DFS(i, adj);

arr.clear();

for (int j = 0; j < n; j++) {

if (vis[j] && i != j) {

arr.push_back(j);

}

res[i] = arr;

}

printResult(res);

}

int main()

{

int N = 5;

vector<vector<int> > Edges

= { { 0, 4 }, { 4, 1 }, { 4, 3 }, { 1, 2 } };

solve(N, Edges);

return 0;

}

Output

0 -> 
1 -> 0 4 
2 -> 0 1 4 
3 -> 0 4 
4 -> 0

Time Complexity: O(V²)
Auxiliary Space: O(|V| + |E|)