First attempt at a question.
Calculating Transitive Closure
According to Wikipedia, "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 is another resource about transitive closure if you still do not fully understand the topic.
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^*\$.
Here's an example (1-indexed):
[[2, 3], , , ]
And this would generate a graph that looks like this:
The first array is vertex
1, and it relates to vertices
2 only relates to
3 only relates to
4 relates to nothing.
Let's take a look at the steps needed to make this graph transitively closed.
1R3 and 3R4, so 1R4 #You can reach 4 from 1, so 1 relates to 4 2R3 and 3R4, so 2R4 #Same goes for 2.
Thus, the correct answer to make this graph \$R^*\$ is
This makes the graph look like this (it is transitively closed):
For completeness, here's what the transitively closed 2D array would look like (but this is not what your program should output):
[[2, 3, 4], [3, 4], , ]
There is an array for every vertex, but your code should be able to account for empty arrays (which means the vertex is originally not connected to any other vertex).
I don't know if this is important, but you can assume the vertices listed in each inner array will be listed in increasing order.
If vertex \$a\$ relates to vertex \$b\$ and vertex \$b\$ relates to vertex \$a\$, then vertex \$a\$ relates to vertex \$a\$ and vertex \$b\$ relates to vertex \$b\$ (Vertices can be related to themselves, it's called reflexive).
Picture of reflexive vertex.
If the graph is already transitive, the program should output 0.
You can use 1 or 0-indexing. Please just specify which.
Many algorithms exist for determining transitive closure. If you'd like an added challenge, attempt this question without researching existing algorithms.
And yeah, that's pretty much it. Here are some test cases (1-indexed):
Input Output [, , ] 0 [, ] 2 [, , ] 2 [, [1, 3], ] 3 [, , [2, 1], ] 5 [[2, 3, 4], [3, 4], , ] 0 [, , , , , ] 30
This question is tagged code-golf. Standard rules apply.