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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Visited array to keep visited marker// for DFS traversalvector<bool> vis;// Function to perform DFS// Traversal on the given graphvoid 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 arrayvoid 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 codeint main(){ int N = 5; vector<vector<int> > Edges = { { 0, 4 }, { 4, 1 }, { 4, 3 }, { 1, 2 } }; // Function Call solve(N, Edges); return 0;} |
Java
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); }} |
Python3
# Python program for the above approach# Visited array to keep visited marker# for DFS traversalvis = []# Function to perform DFS# Traversal on the given graphdef DFS(u, adj): vis[u] = True for v in adj[u]: if not vis[v]: DFS(v, adj)# Function to print the arraydef 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 codeif __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#
// C# program for the above approachusing 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
// JavaScript program for the above approach// Visited array to keep visited marker// for DFS traversallet vis = [];// Function to perform DFS// Traversal on the given graphfunction DFS(u, adj) { vis[u] = true; for (let v of adj[u]) { if (!vis[v]) { DFS(v, adj); } }}// Function to print the arrayfunction 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 codelet N = 5;let Edges = [ [ 0, 4 ], [ 4, 1 ], [ 4, 3 ], [ 1, 2 ] ];// Function Callsolve(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|)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
