Find ancestors of each node in the given Graph
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: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++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Visited array to keep visited marker
// for DFS traversal
vector<bool> vis;
// Function to perform DFS
// Traversal on the given graph
void DFS(int u, vector<vector<int> > adj)
{
vis[u] = 1;
for (int v : adj[u]) {
if (vis[v] == 0)
DFS(v, adj);
}
}
// Function to print the array
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)
{
// Create an adjancency list with
// edges reversed
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);
}
// Resultant vector where for each
// index i from 0 to n-1 the resultant
// sorted ancestors vector for ith
// index will be stored
vector<vector<int> > res(n);
vector<int> arr;
for (int i = 0; i < n; i++) {
// Assign 0 to vis array
vis.assign(n, 0);
// Call DFS for the ith node
DFS(i, adj);
arr.clear();
for (int j = 0; j < n; j++) {
// All the ancestors for node i
// will be visited after DFS call
if (vis[j] && i != j) {
arr.push_back(j);
}
}
// Store the resultant arr in the
// corresponding index
res[i] = arr;
}
printResult(res);
}
// Drivers code
int main()
{
int N = 5;
vector<vector<int> > Edges
= { { 0, 4 }, { 4, 1 }, { 4, 3 }, { 1, 2 } };
// Function Call
solve(N, Edges);
return 0;
}
import java.util.*;
public class Main {
// Visited array to keep visited marker for DFS traversal
static List<Boolean> vis;
// Function to perform DFS Traversal on the given graph
static void DFS(int u, List<List<Integer>> adj) {
vis.set(u, true);
for (int v : adj.get(u)) {
if (!vis.get(v))
DFS(v, adj);
}
}
// Function to print the array
static void printResult(List<List<Integer>> res) {
for (int i = 0; i < res.size(); i++) {
System.out.print(i + " -> ");
for (int j : res.get(i)) {
System.out.print(j + " ");
}
System.out.println();
}
}
static void solve(int n, List<List<Integer>> edges) {
// Create an adjacency list with edges reversed
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (List<Integer> edge : edges) {
int u = edge.get(0), v = edge.get(1);
adj.get(v).add(u);
}
// Resultant vector where for each index i from 0 to n-1
// the resultant sorted ancestors vector for ith index will be stored
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
// Assign false to vis array
vis = new ArrayList<>(Arrays.asList(new Boolean[n]));
Collections.fill(vis, false);
// Call DFS for the ith node
DFS(i, adj);
List<Integer> arr = new ArrayList<>();
for (int j = 0; j < n; j++) {
// All the ancestors for node i will be visited after DFS call
if (vis.get(j) && i != j) {
arr.add(j);
}
}
// Store the resultant arr in the corresponding index
res.add(arr);
}
printResult(res);
}
// Drivers code
public static void main(String[] args) {
int n = 5;
List<List<Integer>> edges = new ArrayList<>();
edges.add(Arrays.asList(0, 4));
edges.add(Arrays.asList(4, 1));
edges.add(Arrays.asList(4, 3));
edges.add(Arrays.asList(1, 2));
// Function Call
solve(n, edges);
}
}
# Python program for the above approach
# Visited array to keep visited marker
# for DFS traversal
vis = []
# Function to perform DFS
# Traversal on the given graph
def DFS(u, adj):
vis[u] = True
for v in adj[u]:
if not vis[v]:
DFS(v, adj)
# Function to print the array
def printResult(res):
for i in range(len(res)):
print(i, "->", end=" ")
for j in res[i]:
print(j, end=" ")
print()
def solve(n, edges):
# Create an adjancency list with
# edges reversed
adj = [[] for i in range(n)]
for i in range(len(edges)):
u, v = edges[i][0], edges[i][1]
adj[v].append(u)
# Resultant vector where for each
# index i from 0 to n-1 the resultant
# sorted ancestors vector for ith
# index will be stored
res = [[] for i in range(n)]
for i in range(n):
# Assign False to vis array
vis.clear()
vis.extend([False] * n)
# Call DFS for the ith node
DFS(i, adj)
arr = []
for j in range(n):
# All the ancestors for node i
# will be visited after DFS call
if vis[j] and i != j:
arr.append(j)
# Store the resultant arr in the
# corresponding index
res[i] = arr
printResult(res)
# Drivers code
if __name__ == "__main__":
N = 5
Edges = [[0, 4], [4, 1], [4, 3], [1, 2]]
# Function Call
solve(N, Edges)
# This code is contributed by Susobhan Akhuli
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Visited array to keep visited marker
// for DFS traversal
static List<bool> vis;
// Function to perform DFS
// Traversal on the given graph
static void DFS(int u, List<List<int> > adj)
{
vis[u] = true;
foreach(int v in adj[u])
{
if (!vis[v]) {
DFS(v, adj);
}
}
}
// Function to print the array
static void printResult(List<List<int> > res)
{
for (int i = 0; i < res.Count; i++) {
Console.Write("{0} -> ", i);
foreach(int j in res[i])
{
Console.Write("{0} ", j);
}
Console.WriteLine();
}
}
static void solve(int n, List<List<int> > edges)
{
// Create an adjancency list with
// edges reversed
List<List<int> > adj = new List<List<int> >(n);
for (int i = 0; i < n; i++) {
adj.Add(new List<int>());
}
foreach(List<int> edge in edges)
{
int u = edge[0], v = edge[1];
adj[v].Add(u);
}
// Resultant List where for each
// index i from 0 to n-1 the resultant
// sorted ancestors list for ith
// index will be stored
List<List<int> > res = new List<List<int> >(n);
vis = new List<bool>(n);
for (int i = 0; i < n; i++) {
vis.Clear();
vis.AddRange(new bool[n]);
// Call DFS for the ith node
DFS(i, adj);
List<int> arr = new List<int>();
for (int j = 0; j < n; j++) {
// All the ancestors for node i
// will be visited after DFS call
if (vis[j] && i != j) {
arr.Add(j);
}
}
// Store the resultant arr in the
// corresponding index
res.Add(arr);
}
printResult(res);
}
// Drivers code
static public void Main()
{
int n = 5;
List<List<int> > edges = new List<List<int> >() {
new List<int>() { 0, 4 },
new List<int>() { 4, 1 },
new List<int>() { 4, 3 },
new List<int>() { 1, 2 }
};
// Function Call
solve(n, edges);
}
}
// This code is contributed by Prasad Kandekar(prasad264)
// JavaScript program for the above approach
// Visited array to keep visited marker
// for DFS traversal
let vis = [];
// Function to perform DFS
// Traversal on the given graph
function DFS(u, adj) {
vis[u] = true;
for (let v of adj[u]) {
if (!vis[v]) {
DFS(v, adj);
}
}
}
// Function to print the array
function printResult(res) {
for (let i = 0; i < res.length; i++) {
console.log(i + " -> " + res[i].join(" "));
}
}
function solve(n, edges) {
// Create an adjancency list with
// edges reversed
let adj = new Array(n).fill(null).map(() => []);
for (let i = 0; i < edges.length; i++) {
let u = edges[i][0], v = edges[i][1];
adj[v].push(u);
}
// Resultant vector where for each
// index i from 0 to n-1 the resultant
// sorted ancestors vector for ith
// index will be stored
let res = new Array(n).fill(null).map(() => []);
let arr = [];
for (let i = 0; i < n; i++) {
// Assign false to vis array
vis = new Array(n).fill(false);
// Call DFS for the ith node
DFS(i, adj);
arr = [];
for (let j = 0; j < n; j++) {
// All the ancestors for node i
// will be visited after DFS call
if (vis[j] && i !== j) {
arr.push(j);
}
}
// Store the resultant arr in the
// corresponding index
res[i] = arr;
}
printResult(res);
}
// Drivers code
let N = 5;
let Edges = [ [ 0, 4 ], [ 4, 1 ], [ 4, 3 ], [ 1, 2 ] ];
// Function Call
solve(N, Edges);
Output
0 -> 1 -> 0 4 2 -> 0 1 4 3 -> 0 4 4 -> 0
Time Complexity: O(V2)
Auxiliary Space: O(|V| + |E|)
Approach 2-Using Topological Sorting and Transitive Closure
The algorithm begins by determining a topological order of nodes, ensuring each node is processed before its descendants. Utilizes dynamic programming to compute the ancestors for each node based on its immediate predecessors, leveraging the transitive property of ancestor relationships. By eliminating the need to perform a separate DFS for each node, this approach reduces redundant computations, making it more efficient for large graphs.
Below is the implementation of above approach:
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Function to find all ancestors of each node in a directed
// acyclic graph (DAG)
void findAncestors(int n, vector<vector<int> >& edges)
{
vector<vector<int> > adj(n); // adjacency list of graph
vector<vector<int> > ancestors(
n); // list of ancestors for each node
vector<int> inDegree(n, 0); // in-degree of each node
queue<int> q; // queue for topological sorting
// Construct the adjacency list and in-degree array
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
inDegree[edge[1]]++;
}
// Enqueue nodes with zero in-degree (no dependencies)
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// Process the graph in topological order
while (!q.empty()) {
int current = q.front();
q.pop();
// For each descendant, reduce its in-degree and
// update its ancestors
for (int descendant : adj[current]) {
// Add all ancestors of current to its
// descendant
for (int ancestor : ancestors[current]) {
if (find(ancestors[descendant].begin(),
ancestors[descendant].end(),
ancestor)
== ancestors[descendant].end()) {
ancestors[descendant].push_back(
ancestor);
}
}
// Add current as an ancestor to its descendant
if (find(ancestors[descendant].begin(),
ancestors[descendant].end(), current)
== ancestors[descendant].end()) {
ancestors[descendant].push_back(current);
}
// Decrease in-degree and enqueue if it's ready
if (--inDegree[descendant] == 0) {
q.push(descendant);
}
}
}
// Print results
for (int i = 0; i < n; i++) {
sort(ancestors[i].begin(),
ancestors[i].end()); // Sort for ordered output
cout << i << " -> ";
for (int ancestor : ancestors[i]) {
cout << ancestor << " ";
}
cout << endl;
}
}
int main()
{
int N = 5;
vector<vector<int> > Edges
= { { 0, 4 }, { 4, 1 }, { 4, 3 }, { 1, 2 } };
// Function Call
findAncestors(N, Edges);
return 0;
}
import java.util.*;
public class FindAncestors {
// Function to find all ancestors of each node in a
// directed acyclic graph (DAG)
public static void
findAncestors(int n, List<List<Integer> > edges)
{
List<List<Integer> > adj
= new ArrayList<>(n); // adjacency list of graph
List<List<Integer> > ancestors = new ArrayList<>(
n); // list of ancestors for each node
int[] inDegree
= new int[n]; // in-degree of each node
Queue<Integer> q
= new LinkedList<>(); // queue for topological
// sorting
// Initialize adjacency list and in-degree array
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
ancestors.add(new ArrayList<>());
}
// Construct the adjacency list and in-degree array
for (List<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
adj.get(u).add(v);
inDegree[v]++;
}
// Enqueue nodes with zero in-degree (no
// dependencies)
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.add(i);
}
}
// Process the graph in topological order
while (!q.isEmpty()) {
int current = q.poll();
// For each descendant, reduce its in-degree and
// update its ancestors
for (int descendant : adj.get(current)) {
// Add all ancestors of current to its
// descendant
for (int ancestor :
ancestors.get(current)) {
if (!ancestors.get(descendant)
.contains(ancestor)) {
ancestors.get(descendant)
.add(ancestor);
}
}
// Add current as an ancestor to its
// descendant
if (!ancestors.get(descendant)
.contains(current)) {
ancestors.get(descendant).add(current);
}
// Decrease in-degree and enqueue if it's
// ready
if (--inDegree[descendant] == 0) {
q.add(descendant);
}
}
}
// Print results
for (int i = 0; i < n; i++) {
Collections.sort(ancestors.get(
i)); // Sort for ordered output
System.out.print(i + " -> ");
for (int ancestor : ancestors.get(i)) {
System.out.print(ancestor + " ");
}
System.out.println();
}
}
public static void main(String[] args)
{
int N = 5;
List<List<Integer> > Edges = Arrays.asList(
Arrays.asList(0, 4), Arrays.asList(4, 1),
Arrays.asList(4, 3), Arrays.asList(1, 2));
// Function Call
findAncestors(N, Edges);
}
}
// This code is contributed by shivamgupta0987654321
from collections import deque
def find_ancestors(n, edges):
# Adjacency list of the graph
adj = [[] for _ in range(n)]
# List of ancestors for each node
ancestors = [[] for _ in range(n)]
# In-degree of each node
in_degree = [0] * n
# Queue for topological sorting
q = deque()
# Construct the adjacency list and in-degree array
for u, v in edges:
adj[u].append(v)
in_degree[v] += 1
# Enqueue nodes with zero in-degree (no dependencies)
for i in range(n):
if in_degree[i] == 0:
q.append(i)
# Process the graph in topological order
while q:
current = q.popleft()
# For each descendant, reduce its in-degree and update its ancestors
for descendant in adj[current]:
# Add all ancestors of current to its descendant
for ancestor in ancestors[current]:
if ancestor not in ancestors[descendant]:
ancestors[descendant].append(ancestor)
# Add current as an ancestor to its descendant
if current not in ancestors[descendant]:
ancestors[descendant].append(current)
# Decrease in-degree and enqueue if it's ready
in_degree[descendant] -= 1
if in_degree[descendant] == 0:
q.append(descendant)
# Print results
for i in range(n):
ancestors[i].sort() # Sort for ordered output
print(f"{i} -> {' '.join(map(str, ancestors[i]))}")
# Test case
N = 5
Edges = [(0, 4), (4, 1), (4, 3), (1, 2)]
# Function Call
find_ancestors(N, Edges)
function findAncestors(n, edges) {
// Adjacency list of the graph
const adj = Array.from({ length: n }, () => []);
// List of ancestors for each node
const ancestors = Array.from({ length: n }, () => []);
// In-degree of each node
const inDegree = Array(n).fill(0);
// Queue for topological sorting
const q = [];
// Construct the adjacency list and in-degree array
edges.forEach(([u, v]) => {
adj[u].push(v);
inDegree[v]++;
});
// Enqueue nodes with zero in-degree (no dependencies)
for (let i = 0; i < n; i++) {
if (inDegree[i] === 0) {
q.push(i);
}
}
// Process the graph in topological order
while (q.length > 0) {
const current = q.shift();
// For each descendant, reduce its in-degree and update its ancestors
adj[current].forEach((descendant) => {
// Add all ancestors of current to its descendant
ancestors[descendant].push(...ancestors[current]);
// Remove duplicates
ancestors[descendant] = Array.from(new Set(ancestors[descendant]));
// Add current as an ancestor to its descendant
ancestors[descendant].push(current);
// Decrease in-degree and enqueue if it's ready
inDegree[descendant]--;
if (inDegree[descendant] === 0) {
q.push(descendant);
}
});
}
// Sort ancestors for ordered output
const result = [];
for (let i = 0; i < n; i++) {
ancestors[i].sort((a, b) => a - b);
result.push(`${i} -> ${ancestors[i].join(' ')}`);
}
// Print results or return as desired
console.log(result.join('\n'));
}
// Test case
const N = 5;
const Edges = [
[0, 4],
[4, 1],
[4, 3],
[1, 2]
];
// Function Call
findAncestors(N, Edges);
Output
0 -> 1 -> 0 4 2 -> 0 1 4 3 -> 0 4 4 -> 0
Time Complexity: O(V+E) where V is the number of vertices and E is the number of edges. This complexity arises from constructing the adjacency list and performing the topological sort and ancestor accumulation.
Auxilary Space: O(V+E) to store the adjacency list, in-degree array, and the queue, along with the ancestor lists.