Kotlin. Beats 100% (811 ms). OOP + simple DFS.
\n\n# Code\n\nclass Solution {\n    fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {\n        val nodes = Array(n) { GNode(it) }\n\n        f
![image.png](https://assets.leetcode.com/users/images/d743099d-bce4-457b-8c1a-2681874b5d15_1719678860.7882962.png)\n\n# Code\n```\nclass Solution {\n    fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {\n        val nodes = Array(n) { GNode(it) }\n\n        for ((from, to) in edges) {\n            nodes[from].links.add(nodes[to])\n        }\n\n        for (i in 0 until n) {\n            for (child in nodes[i].links) {\n                dfs(child, i)\n            }\n        }\n\n        val result = ArrayList<List<Int>>()\n        for (i in 0 until n) {\n            result.add(nodes[i].ancestors)\n        }\n        return result\n    }\n\n    private fun dfs(node: GNode, ancestor: Int) {\n        if (node.last == ancestor) return\n        node.last = ancestor\n        node.ancestors.add(ancestor)\n        for (child in node.links) {\n            dfs(child, ancestor)\n        }\n    }\n\n    class GNode(val index: Int) {\n        var last: Int = -1\n        val ancestors = ArrayList<Int>()\n        val links = ArrayList<GNode>()\n    }\n}\n```\n\nIn this problem, we must solve two problems:\n\n1) Find all ancestors of every graph node\n2) At the same time, observe the order of sorting.\n\nTo fulfill both conditions, we can first form a graph using an object-oriented approach, where each graph node is an instance of a specific class "GNode".\n\nFirst we just need to form a graph using the class GNode:\n```\nclass GNode {\n    val links = ArrayList<GNode>()\n}\n```\n\nAfter the class is created, we can write a code that forms a graph in an object-oriented form:\n\n```\nval nodes = Array(n) { GNode() }\n\nfor ((from, to) in edges) {\n    nodes[from].links.add(nodes[to])\n}\n```\n\nBut this only creates the structure of the graph. To solve the problem, we also need to add another field to each node of the graph - a list of ancestors:\n\n```\nclass GNode {\n    val ancestors = ArrayList<Int>()\n    val links = ArrayList<GNode>()\n}\n```\n\nAnd write a recursive algorithm, which first adds the "0" node to every node that is "reachable" from "0" node. Then we recursively repeat the same operation for the "1" node and others:\n\n```\nfun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {\n    val nodes = Array(n) { GNode() }\n\n    for ((from, to) in edges) {\n        nodes[from].links.add(nodes[to])\n    }\n\n    for (i in 0 until n) {\n        for (child in nodes[i].links) {\n            dfs(child, i)\n        }\n    }\n\n    val result = ArrayList<List<Int>>()\n    for (i in 0 until n) {\n        result.add(nodes[i].ancestors)\n    }\n    return result\n}\n\nprivate fun dfs(node: GNode, ancestor: Int) {\n    node.ancestors.add(ancestor)\n    for (child in node.links) {\n        dfs(child, ancestor)\n    }\n}\n\nclass GNode {\n    val ancestors = ArrayList<Int>()\n    val links = ArrayList<GNode>()\n}\n```\n\nBut there is one small trap: during the DFS, we can get into the same node twice (first through a shorter path, then through a longer one). And then we will have "doubles" (repeated values) in our list, which we would like to avoid:\n\n```\n[[], [], [], [0, 1], [0, 2], [0, 1, 3], [0, 0, 1, 2, 3, 4], [0, 1, 2, 3]]\n\n// [0, 0, 1, 2, 3, 4]\n```\n\nTo remove doubles, we can store the last added element in each node:\n```\nclass GNode {\n    var last: Int = -1\n    val ancestors = ArrayList<Int>()\n    val links = ArrayList<GNode>()\n}\n```\n\nAnd check before adding whether the same element was added earlier.\n\n```\nif (node.last == ancestor) return\nnode.last = ancestor\n```
['Kotlin']