[Question]
  [
First attempt at a question.
---
# Calculating Transitive Closure
![](https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Complete_graph_K7.svg/300px-Complete_graph_K7.svg.png)
According to [Wikipedia](https://en.wikipedia.org/wiki/Transitive_closure), "the transitive closure \$R^\*\$ of a homogeneous binary relation \$R\$ on a set \$X\$ is the smallest relation on \$X\$ that contains \$R\$ and is transitive."
Also, "a relation \$R\$ on a set \$X\$ is transitive if, for all \$x, y, z \in X\$, whenever \$x R y\$ and \$y R z\$ then \$x R z\$."
If that jargon did not make much sense, just remember the transitive law:
> 
> If \$a = b\$ and \$b = c\$, then \$a = c\$.
> 
> 
> 
We can use this law for relations on sets.
Basically, transitive closure provides reachability information about a graph. If there is a path from \$a\$ to \$b\$ (\$a\$ "reaches" \$b\$), then in a transitively closed graph, \$a\$ would relate to \$b\$.
[Here](https://www.techiedelight.com/transitive-closure-graph/) is another resource about transitive closure if you still do not fully understand the topic.
---
# Challenge
Given a 2D Array (representing the graph \$R\$) where each inner array contains only positive integers and represents a vertex, **determine the number of additional edges required to create the transitively closed graph \$R^\*\$.**
---
  
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~17~~ 16 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
āεFè]øε˜ÙINèK}˜g
```
0-based indexing.
[Try it online](https://tio.run/##yy9OTMpM/f//SOO5rW6HV8Qe3nFu6@k5h2d6@h1e4V17ek76///R0YY6RrE60SBsDMSxsQA) or [verify all test cases](https://tio.run/##S0oszvifnFiiYKeQnJ@SqpdfnJiUmapgY6Pg6u/GZa@k8KhtkoKSvdL/I43ntrodXhF7eMe5rafnHJ7p6Xd4hXft6Tnp/5X0wnS4QKq5yjMyc1IVilITUxQy87hS8rkUFPTzC0r0IYZCKTR7bBRUwGrzUv9HRxvqGMXqRIOwMRDHxnJFR4NoKNMQyDBAYiELgzWCuUYQHYY6BmCjwCp0jHRABkJIY2SNMLtMgNgUaj4A) or [see what it does step-by-step](https://tio.run/##VVHNSsNAEL77FENOCilFvSmSW6WIIh4tOYzJNFnY7MbsbGsPPfgYQh@gL6B4Nt4KvlK6P0rxMMsyzPcz32iDT4KGIZmq1vIFJOnV10d2lNxbUwOCFIZBKOCaoENVEcxOU9dwsyNJquI695jv14i6xRb0gjogLGpYoLSUAqoSFBmm0gFLenEv68AYeNwPGRpUK2DRkPF8P@@TfptHzkfRjtlpm1YbugSzxLYVqoJOL8240NI2KmD6zzg/kchMKshaJZ6tmK@iH6GUs@ZXihq7Tf@2jqAHapzvg6lR8G7gOMmmWXIC8043keQAn97125v1f1G3WEUceEJ0eg5YloKFVijlCoqO0AdRaOel8O3gfbeJNNd/2BCtR3MtTArLWnj/BrTtoCNjJfsItOXfo1XZMMzcac7ydObr3FWe7wE).
**Explanation:**
```
ā           # Push a list in the range [1, (implicit) input-length]
 ε          # Map over each value:
  F         #  Loop that many times:
   è        #   Index the inner-most values of the current list into the (implicit)
            #   input-list,
            #   which will use the (implicit) input-list in the first iteration
 ]          # Close both the loop and map
  ø         # Zip/transpose; swapping rows/columns
   ε        # Map over each inner nested list:
    ˜       #  Flatten it
     Ù      #  Uniquify its values
      INè   #  Push the map-index'th list of the input
         K  #  Remove those values from the current list
   }˜       # After the map: flatten it to get all additionally created connections
     g      # Pop and push the length
            # (after which this amount is output implicitly as result)
```
Initially I used `.Γè}` instead of `āεFè]`, and although it worked for the [example test case](https://tio.run/##yy9OTMpM/f9f79zkwytqD@84t/X0nMMzPf0Or/CuPT0n/f//6GhDHaNYnWgQNgbi2FgA), it didn't for any test cases that have reflexive vertices (like test case `[[1],[0]]` for example). Hence the use of `āεFè]` to loop a fixed amount of times based on the amount of input-vertices.
[Answer]
# [Itr](https://github.com/bsoelch/OneChar.js/blob/main/ItrLang.md), 11 bytes *(non competing)*
`#µÍ®ääe*¿<S`
Reads zero-indexed array from standard input, prints the solution to standard output
[online interpreter](https://bsoelch.github.io/OneChar.js/?lang=itr&src=I7XNruTkZSq_PFM=&in=W1sxLDJdLFsyXSxbM10sW11d)
# Explanation
The solution is based on the observation that an entry `i,j` of the `k`-th power of the adjacency matrix of a graph taken is nonzero iff there is a walk of length `k` in the graph connecting the vertices `i` and `j`.
So the adjacency matrix of the transitive closure has ones in all entries that are non-zero in at least one positive power of the adjacency matrix of the original graph.
```
#             ; read the array from standard input
 µÍ®          ; compute adjacency matrix of graph
 µ            ; apply to all elements
  Í           ; convert array to array with ones at the indices given by the values of the array
   ®          ; convert nested array to matrix
    ää        ; duplicate matrix twice
      e       ; compute matrix exponential (sum of all powers of matrix)
       *      ; multiply with original matrix (sum of all positive powers of matrix)
        ¿     ; replace all non-zero entries with one
         <    ; point-wise comparison keeps only the entries that appear in A*e^A but not in A 
          S   ; sum up all entries (as all entries are zero or one, this give the number of nonzero entries)
              ; solution is implicitly printed
```
## Disclaimer
*This language was created after I saw the sandbox version of this challenge.
While the [general consensus](https://codegolf.meta.stackexchange.com/questions/12877/lets-allow-newer-languages-versions-for-older-challenges) seems to be that new languages without built-ins designed specifically for a challenge are allowed,
I will still mark this solution as non-competing as this challenge heavily influenced the design process
(for instance built-in matrix operations and the `Í` operator were introduced to simplify writing this solution)*
---
# Itr, [12 bytes](https://bsoelch.github.io/OneChar.js/?lang=itr&src=I7XNruRMuV5TvzxT&in=W1sxLDJdLFsyXSxbM10sW11d) (no floating point operations)
`#µÍ®äL¹^S¿<S`
`L¹^S` directly computes the sum of the first n powers
```
  ^  ; the matrix to the power of
L¹   ; the range from 1 to the number of rows (does not consume the array)
   S ; sum up all results (taking to the power of a vector will give a vector containing all the powers)
```
[Answer]
# JavaScript (ES6), 74 bytes
Uses 0-based indexing. Returns `false` for `0`.
```
f=a=>a.some(b=>b.some(i=>a[i].some(v=>!b.includes(v)&&b.push(v))))&&1+f(a)
```
[Try it online!](https://tio.run/##dZDBcoMgEIbvPsX24sDUkChJLw7e@hSOh8VoY8aIExounT67XSBt0zbdGZaf5eOH5YgObXse5tfVZPbdsvQKVYXCmlPHtKp0VAPV6qGJC6eqBy2GqR0v@84yx9NUi/liDyQp0jR/7BnypawTgLpuMoiD0t9Yr2ETsMIz@X0oYMUt9o/fLywDeZckTAZMfj6uyCCYyluWsF10I6MMtgG4zttv458tyK/dnU9P17bipZukSURvzs/YHhiCquCNTpIAFCecmfYlHaTz0sEKcs5LglozWTN2YjQvzH8vFd95uXwA "JavaScript (Node.js) – Try It Online")
### How?
We look for some sub-list `b` in the main list `a` and some `i` in `b` such that there's at least one value `v` in the sub-list `a[i]` that does not yet exist in `b`. If `v` is found, we add it to `b` and increment the final result. This process is repeated until there's nothing to update anymore.
### Commented
```
f =                  // f is a recursive function taking ...
a =>                 // ... the main list a[]
a.some(b =>          // for each sub-list b[] in a[]:
  b.some(i =>        //   for each value i in b[]:
    a[i].some(v =>   //     for each value v in a[i]:
      !b.includes(v) //       if v is not already in b[],
      && b.push(v)   //       append v to b[] and trigger all some()'s
    )                //     end of some()
  )                  //   end of some()
)                    // end of some()
&& 1 +               // if truthy, increment the final result
f(a)                 // and do a recursive call with the updated list
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 12 bytes
```
ls-Vum{sam@G
```
[Try it online!](https://tio.run/##K6gsyfj/P6dYN6w0t7o4MdfB/f//6GijWB2FaBA21FEwANFGsbEA "Pyth – Try It Online")
Takes zero-indexed input.
### Explanation
This may be the most implicitly added variables I've ever had in a Pyth golf.
```
ls-Vum{sam@GkddGQQ    # implicitly add kddGQQ
                      # implicitly assign Q = eval(input())
    u           Q     # find fixed point, repeatedly apply lambda G, H to the previous value, iteration number until we get a result that has occurred before, begin with Q
     m         G      #   map lambda d over G
         m   d        #     map lambda k over d
          @Gk         #       value of G at index k
        a     d       #     append d
       s              #     flatten
      {               #     deduplicate
  -V             Q    # remove any elements originally present in Q, vectorized
 s                    # flatten
l                     # output the length
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
;ịFQʋ€ÐLḟ"⁸FL
```
A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R\*\$, containing \$R\$.
**[Try it online!](https://tio.run/##y0rNyan8/9/64e5ut8BT3Y@a1hye4PNwx3ylR4073Hz@//8fHW0Uq6MQbQwiTECEKYgwAxGGsbEA "Jelly – Try It Online")** Or see the [test-suite](https://tio.run/##y0rNyan8/9/64e5ut8BT3Y@a1hye4PNwx3ylR4073Hz@H530cOcMncPtWY8a5ijY2ik8apirGfn/f3R0dKyOAgTH6nApREcbgdiGqBx0WR0FYyQxY5gJRjoKYLXGMMVAdToKJmAhKG2CbpYxXNQURJjBbY8FAA "Jelly – Try It Online").
### How?
Repeatedly add edges that do not yet exist for all traversable pairs of edges, then count the number of new edges.
```
;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A
      ÐL      - start with X=A and loop until a fixed point applying:
     €        -   for each {node in X}:
    ʋ         -     last four links as a dyad - F(node, X)
 ị            -       {node} index into {X} (vectorises)
;             -       {node} concatenate {that}
  F           -       flatten
   Q          -       deduplicate -> updated node
          ⁸   - chain's left argument -> A
         "    - zip with:
        ḟ     -   {final node} filter discard {original node from A}
           F  - flatten
            L - length
```
---
The end, `ḟ"⁸FL`, seems long, is there something better than this or `;ịFQʋ€ÐLn>0SS` etc.?
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), 110 bytes
```
f=lambda a,o=0,c=0:a!=(m:=[[*(s:={*sum([a[i]for i in n],n)},c:=c+len(s-{*n}))[0]]for n in a])and c+f(m,o or a)
```
A recursive function that accepts the adjacency list, `a`, and returns the number of required edges (with `False` [quacking like](https://codegolf.meta.stackexchange.com/a/9067/53748 "meta") `0`).
**[Try it online!](https://tio.run/##bZDRasMwDEXf9xVan@xEBbduxzBoP2LM8NKaGRolJNnDCPn2LHa70LEabKOro4uk9nv4bFi/tt08B7r4@uPkwWNDCitSxj@TqA1ZW4je0Fj0X7Ww3kYXmg4iRAZ2yHLCylBVXs4s@u1Y8CSlVS5DnCDvpOcTVGUQNTawyF7OKTuc@yEB4gmWY61DuF6HN2Wfwt2/@AGDoP/K@tdtj5Ar9F3JQiMcsnr7Dw9M9Zo4pudlbUaajKX@3xXQwsftDu62AuvwiXGZbrvIgwibMUkT0BuMQVwtZKmmjZx/AA "Python 3.8 (pre-release) – Try It Online")**
[Answer]
# Python3, 240 bytes:
```
E=enumerate
T=lambda K,g:[(v,l)for i,v in E(K)for _,l in E(K[i+1:])if l not in g[v-1]]
def e(g,n,c=[]):
 for i in g[n-1]:
  yield from T(c+[n,i],g)
  if i not in c:yield from e(g,i,c+[n])
f=lambda g:len({j for i,_ in E(g)for j in e(g,i+1)})
```
[Try it online!](https://tio.run/##dU@7bsMgFN35ijuCfDs4pFVlyWOmrNkQilwbKBHGluVaiqp@uwvY7jMZAN3zuof@Or52nj/3wzwfSuXfWjVUoyKn0lXtS1PBEU0h6ISO6W4AixNYDwd6TOMZ3ToKm@WFZFaDA9@NETViesilJI3SoKhBj3UpJCsIpKRF4oMkIHC1yjWgh66FE60z4dFKNCwwIdJukXXxQxczLUatZERvfU3hlKfvl2UJnpd@JtW9xCHZspx9sLkfrB@ppkJIhOVIxsg3vItY@APcQu/JEfgNjm8rdgjJy/@agw9hn6j13d/bwb/Yx3g9rTX/5f3WRsH8CQ)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 18 bytes
```
ＦθＦιＦ⁻§θκι«⊞ιλ→»Ｉⅈ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z8tv0hBo1BTAUxnQmjfzLzSYg3HEs@8lNQKjUIdhWxNHQWgXDUXZ0BpcYZGpo5CjqY1F6dvflmqhlVQZnpGCZBbyxVQlJlXouGcWFyiEaGhqalp/f9/dHS0UayOQjQIG@ooGIBoo9jY2P@6ZTkA "Charcoal – Try It Online") Link is to verbose version of code. `0`-indexed. Explanation:
```
Ｆθ
```
Loop over each vertex.
```
Ｆι
```
Loop over the list of target indices for this vertex. Note that this list can be extended by the innermost loop in which case the additional indices will also be considered.
```
Ｆ⁻§θκι«
```
Loop over the list of target indices for the target vertex, but exclude indices already present in the list of target indices for the source vertex.
```
⊞ιλ
```
Add this index to the list of target indices for the source vertex.
```
→
```
Increment a counter.
```
»Ｉⅈ
```
Output the final count.
Bonus: Reflexive closure, 8 bytes:
```
ＩΣＥθ¬№ικ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRMM5sbhEI7g0V8M3sUCjUEfBLx8oll8KlMnUUcjWBAPr//@jo6MNYnUUokEYzDCMjY39r1uWAwA "Charcoal – Try It Online") Link is to verbose version of code.
Bonus 2: Symmetric closure, 14 bytes:
```
ＩΣＥθ↨¹Ｅι¬№§θλκ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRMM5sbhEI7g0V8M3sUCjUEfBKbE4VcNQRwHEzdRR8MsHKskvBSp0LPHMS0mtAKnJ0dRRyNaEAuv//6Ojo41idRSiQRio1QBEG8XGxv7XLcsBAA "Charcoal – Try It Online") Link is to verbose version of code.
[Answer]
# [Nekomata](https://github.com/AlephAlpha/Nekomata) + `-n`, 16 bytes
```
~ᵉ{$#ᵑ{ˣ@j,u}}∕~
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iLzU7PzexJHFNtJJurpKOgpJunlLsgqWlJWm6FtvrHm7trFZRfrh1YvXpxQ5ZOqW1tY86ptYtKU5KLoaqWXCzJDo6VgeMYrmiow2BDAMkFrKwjhGMawTRYagDUmAEUaFjpGMM4oFJY2SNRlABEyA2hZgPsRwA)
[Answer]
# [Scala](https://www.scala-lang.org/), 102 bytes
Port of [@CursorCoercer's Python answer](https://codegolf.stackexchange.com/a/263589/110802) in Scala.
---
Golfed version. [Try it online!](https://tio.run/##jVFNa8MwDL3nV4jSg0WdkDXdDksd2HGwnXYcJbiZ02XEThabMhb82zM7JaXrPujB0rPe00OWdcFrPjTbN1EYeOSVAvFhhHrRcNe20AfBntdQ3pIn8f7sz70ymw3LXEJgA2dZv@cdkVQjcxoz8gRpjGnZdEStQ469ZCoyjWPHWu5q6W4dSuw52WHkaoIXr0QuWI42lWHIVKoXTEa6@hQ21XYIAPwYRmijgcFDpQ1xNTigMSCF7xnpmWI5UVf/chf0U0j@liXnkywpHF2TX2ydG4XVUXGCVxcMk/wQX0/g5uTBrh0DF8YVHlfub8Ay983efVpx7FbscyR5S5Tn1QhzCOFgBdB2lTK1Ino2n0zmfTkaxmhnXmQxsMMX)
```
a=>{var(m,s)=(Set[Int](),0);for(n<-a){m=n.toSet;for(_<-a;g<-m){a(g).foreach(m+=_)};m--=n;s+=m.size};s}
```
Ungolfed version. [Try it online!](https://tio.run/##jZJdT4MwFIbv@RVvll20EQiO6cUUEy9N9MpLs5COlYmBQmhjjAu/HdsC3Zwf2U3P13PenJ5WZqxkfV9v3nim8MQKAf6huNhK3DcN9h6w5TlywlZ4LKR6sceDUOs1XUFbJBYC3lmLSkfPfKgT6tJSpyMb5XULInAbgNGxD7ZLhKrWnWPGYqnFbrAztjrgACM7GmqGs@yVVLhIkNKx2DnNINCqYyQNU4Wy@OTegZKe8TwzYwnFpTJzmvsRW7aePaiP75b6J8RiKl3@Wzuj30f8NxafTrLw4VTjX2S1mo@lI4785RnDxD/gq8m5PrqwbqdmjXaF7l1MhOTO/Y5hxZFesbFhxRr9EXRdWDdFgEEKaNpCqFIQOZtPIvN9bgUj2s0M1FGv8/r@Cw)
```
object Main extends App {
  def f(a: List[List[Int]]): Int = {
    var m = Set[Int]()
    var s = 0
    for (n <- a) {
      m = n.toSet
      for (_ <- a; g <- m) {
        a(g).foreach(m += _)
      }
      m --= n
      s += m.size
    }
    s
  }
  val tests = List(
    List(List(), List(), List()),
    List(List(2), List(1)),
    List(List(2), List(1), List()),
    List(List(2), List(1, 3), List()),
    List(List(3), List(), List(2, 1), List(3)),
    List(List(2, 3, 4), List(3, 4), List(4), List()),
    List(List(2), List(3), List(4), List(5), List(6), List(1))
  )
  tests.foreach(test => {
    val test0 = test.map(n => n.map(_ - 1))
    println(s"$test => ${f(test0)}")
  })
}
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 18 bytes
```
Fi"TX@@g&(]tYezwz-
```
The input is a cell array of numerical vectors, 1-based. [Try it online!](https://tio.run/##y00syfn/3y1TKSTCwSFdTSO2JDK1qrxK9///6mijWB2FaGMQYQIiTEGEGYgwjK0FAA "MATL – Try It Online") Or [verify all test cases](https://tio.run/##y00syfmf8N8tUykkwsEhXU0jtiQytaq8Sve/S8j/6uhYHQUIruWqjjYCsQyRmagyOgrGcBFjmE4jHQWwOmOIQqAaHQUTsACUNkE1xRguZgoizKB2AgA).
### Explanation
The first 11 bytes are used for computing the adjacency matrix from the specified input format. The rest of the code is essentially comparing the matrix before and after matrix exponentiation.
```
F       % Push false, that is, a 1x1 logical matrix containing false
i       % Push input: cell array of numerical vectors
"       % For each entry in the cell array
  T     %   Push true (*)
  X@    %   Push current iteration index, starting at 1 (**)
  @g    %   Push current numerical vector (***)
  &(    %   Write true (*) at specified row (**) and column indieces (***)
        %   in the logical matrix. This may increase the matrix size
]       % End. The stack now contains the adjacency matrix
t       % Duplicate adjacency matrix
Ye      % Compute the logical version of the adjacency matrix of the power
        % of the graph with increasing exponent until the result no longer
        % This is the same as logical(M*expm(M)), where M is the original
        % adjacency matrix and expm is matrix exponeitial, but numerical
        % precision issues are avoided
z       % Number of nonzeros
w       % Swap. Moves copy of original adjacency matrix to top
z       % Number of nonzeros
-       % Subtract. Implicit display
```
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), 84 bytes
```
lambda a:sum(len((m:={*n},[m:=m|{*a[g]}for f in a for g in m])and m-{*n})for n in a)
```
[Try it online!](https://tio.run/##bY9hC4IwEIa/9ysOP20yIZ1FCPZHbMRCZ4KbovYhzN9u3jQpcrDtvfeeO@7qZ3evDD/Vzajiy1hKfUslyKh9aFJmhhAdxb1rBpZMQr96Vya5GFTVgILCgASUOUotqDQpaA9xiraxBB1Rd1nbYUh2MJ0kEQzmK9jiBBj6f/EGw4D/2vzTLWBgK/hXyUQzCK27/OFGU74mDvgc12FoZDGc/7qHeOILz7dbF7iPEbCuioywdN0UpiPK6dEaID5Dr8jcgg4OHd8 "Python 3.8 (pre-release) – Try It Online")
Takes 0-indexed input. Essentially a port of my [Pyth answer](https://codegolf.stackexchange.com/a/263579/73054) with some swapping of loop order.
[Answer]
# [J](http://jsoftware.com/), 36 bytes
```
[:+/@,@((+/ .*+.])^:_~-])<@i.@#e.&>]
```
[Try it online!](https://tio.run/##VY3BCsIwEETv/Yqhim1Muk1TvSStBARPnrxK9CAp6sU/8NdjQi20LLvLPmZm3yGnYkCvUUBAQseuCMfL@RSumtdW2LLkNWjLybGbvn8rxzr7IrvytDm4wDLfk1zLzD@eHwzwJtZ0lKJhMHFJNqEGKgE18pYZLNQm/lcLppIk4cZAKGAWhDaGjDNFYebrrMj5X7PDHjL8AA "J – Try It Online")
Uses 0 indexing.
* `<@i.@#e.&>]` Convert adjacency list to adjacency matrix
* `(+/ .*+.])^:_~` Take transitive closure of matrix multiplication, but any cell that becomes 1 also remains 1 `+.]`.
* `-]` Subtract original adj matrix
* `+/@,@` Count the ones
]