DEV Community

Cover image for 2192. All Ancestors of a Node in a Directed Acyclic Graph
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

2192. All Ancestors of a Node in a Directed Acyclic Graph

2192. All Ancestors of a Node in a Directed Acyclic Graph

Medium

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Example 1:

e1

  • Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
  • Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
  • Explanation: The above diagram represents the input graph.
    • Nodes 0, 1, and 2 do not have any ancestors.
    • Node 3 has two ancestors 0 and 1.
    • Node 4 has two ancestors 0 and 2.
    • Node 5 has three ancestors 0, 1, and 3.
    • Node 6 has five ancestors 0, 1, 2, 3, and 4.
    • Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

e2

  • Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
  • Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
  • Explanation: The above diagram represents the input graph.
    • Node 0 does not have any ancestor.
    • Node 1 has one ancestor 0.
    • Node 2 has two ancestors 0 and 1.
    • Node 3 has three ancestors 0, 1, and 2.
    • Node 4 has four ancestors 0, 1, 2, and 3.

Constraints:

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • There are no duplicate edges.
  • The graph is directed and acyclic.

Solution:

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @return Integer[][]
     */
    function getAncestors($n, $edges) {
        $adjacencyList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $from = $edge[0];
            $to = $edge[1];
            $adjacencyList[$to][] = $from;
        }

        $ancestorsList = [];

        for ($i = 0; $i < $n; $i++) {
            $ancestors = [];
            $visited = [];
            $this->findChildren($i, $adjacencyList, $visited);
            for ($node = 0; $node < $n; $node++) {
                if ($node == $i) continue;
                if (in_array($node, $visited))
                    $ancestors[] = $node;
            }
            $ancestorsList[] = $ancestors;
        }

        return $ancestorsList;
    }

    private function findChildren($currentNode, &$adjacencyList, &$visitedNodes) {
        $visitedNodes[] = $currentNode;
        foreach ($adjacencyList[$currentNode] as $neighbour) {
            if (!in_array($neighbour, $visitedNodes)) {
                $this->findChildren($neighbour, $adjacencyList, $visitedNodes);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Retry later