Problem 1260
A Simple Problem
Time Limit: 2000ms
Memory Limit: 65536kb
This is a simple problem. Given n nodes labeled from 1 to n in a directed graph. Some nodes are currently connected by some one-way edges. Now your task is to add least edges to meet the condition that regardless of the starting node from which, there will always be at least one path back to the starting node.
The first line contains an integer T (1<=T<=50) which indicates there are T test cases.
To every case:
The first line contains an integer N (1<=N<=20), which indicates the number of the nodes in a directed graph.
Then one N by N matrix with its element 0 or 1 is followed. If the j-th column of the i-th line is 1, then there is always a one-way from i to j.
To every test case, output the least number of edges you need add.
Sample Input
0 1 0
0 0 1
0 1 1
Sample Output
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).