<commit_before>package leetcode

import java.util.*

/**
 * https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
 */
class Problem2192 {
    fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {
        val adjList = reverse(n, edges)
        val answer = mutableListOf<List<Int>>()
        for (i in 0 until n) {
            val ancestors = TreeSet<Int>()
            getAncestors(i, adjList, ancestors)
            answer += ancestors.toList()
        }
        return answer
    }

    private fun reverse(n: Int, edges: Array<IntArray>): Array<MutableList<Int>> {
        val adjList = Array<MutableList<Int>>(n) { mutableListOf() }
        for (edge in edges) {
            val from = edge[0]
            val to = edge[1]
            adjList[to].add(from)
        }
        return adjList
    }

    private fun getAncestors(i: Int, adjList: Array<MutableList<Int>>,
                             ancestors: TreeSet<Int>) {
        for (adjacent in adjList[i]) {
            ancestors += adjacent
            getAncestors(adjacent, adjList, ancestors)
        }
    }
}

fun main() {
    val prob = Problem2192()
    println(prob.getAncestors(8, arrayOf(
        intArrayOf(0,3), intArrayOf(0,4), intArrayOf(1,3), intArrayOf(2,4), intArrayOf(2,7),
        intArrayOf(3,5), intArrayOf(3,6), intArrayOf(3,7), intArrayOf(4,6)
    ))) // [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
    println(prob.getAncestors(5, arrayOf(
        intArrayOf(0,1), intArrayOf(0,2), intArrayOf(0,3), intArrayOf(0,4), intArrayOf(1,2),
        intArrayOf(1,3), intArrayOf(1,4), intArrayOf(2,3), intArrayOf(2,4), intArrayOf(3,4)
    ))) // [[],[0],[0,1],[0,1,2],[0,1,2,3]]
}<commit_msg>Solve problem 2192<commit_after>package leetcode

import java.util.*

/**
 * https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
 */
class Problem2192 {
    fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {
        val adjList = reverse(n, edges)
        val answer = mutableListOf<List<Int>>()
        for (i in 0 until n) {
            val ancestors = mutableListOf<Int>()
            val visited = BooleanArray(n)
            getAncestors(i, adjList, ancestors, visited)
            ancestors.sort()
            answer += ancestors
        }
        return answer
    }

    private fun reverse(n: Int, edges: Array<IntArray>): Array<MutableList<Int>> {
        val adjList = Array<MutableList<Int>>(n) { mutableListOf() }
        for (edge in edges) {
            val from = edge[0]
            val to = edge[1]
            adjList[to].add(from)
        }
        return adjList
    }

    private fun getAncestors(i: Int, adjList: Array<MutableList<Int>>,
                             ancestors: MutableList<Int>, visited: BooleanArray) {
        visited[i] = true
        for (adjacent in adjList[i]) {
            if (!visited[adjacent]) {
                ancestors += adjacent
                getAncestors(adjacent, adjList, ancestors, visited)
            }
        }
    }
}
{'fraction_non_alphanumeric': 0.14941022280471822, 'fraction_numerical': 0.028833551769331587, 'mean_word_length': 2.343921139101862, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 31, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5817560', 'n_tokens_mistral': 1072, 'n_tokens_neox': 1040, 'n_words': 198}