
82  ZOJ Monthly, August 2009  B
When a directed graph is given, we can solve its transitive closure easily using the wellknown Floyd algorithm. But if you're given a transitive closure, can you give a corresponding directed graph with minimal edges? InputAbout 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 01 matrix form, each line has N numbers. OutputFor each case, just output the number of minimal edges of a directed graph which has a given transitive closure. Sample Input1 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 T_{i,j} is true if and only if there is a path from vertex i to j. Author: CUI, Tianyi 