| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1260
A Simple Problem
Time Limit: 2000ms
Memory Limit: 65536kb Description
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.
Input
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. Output
To every test case, output the least number of edges you need add.
Sample Input
1 3 0 1 0 0 0 1 0 1 1 Sample Output
1 |