ZOJ Problem Set - 3232
When a directed graph is given, we can solve its transitive closure easily using the well-known Floyd algorithm.
But if you're given a transitive closure, can you give a corresponding directed graph with minimal edges?Input
About 100 test cases, seperated by blank line.
First line of each case is an integer N (1<=N<=200). The following N lines represent the given transitive closure in 0-1 matrix form, each line has N numbers.Output
For each case, just output the number of minimal edges of a directed graph which has a given transitive closure.Sample Input
1 1 2 1 0 0 1 2 1 1 1 1 3 1 1 1 0 1 1 0 0 1Sample Output
0 0 2 2Hint
Transitive closure can be presented as a matrix T, where Ti,j is true if and only if there is a path from vertex i to j.
Author: CUI, Tianyi
Source: ZOJ Monthly, August 2009