D |
Dominator |
In graph theory, a node X dominates a node Y if every path from the predefined start node to Y must go through X. If Y is not reachable from the start node then node Y does not have any dominator. By definition, every node reachable from the start node dominates itself. In this problem, you will be given a directed graph and you have to find the dominators of every node where the 0th node is the start node.
As an example, for the graph shown right, 3 dominates 4 since all the paths from 0 to 4 must pass through 3. 1 doesn't dominate 3 since there is a path 0-2-3 that doesn't include 1.
The first line of input will contain T (≤ 100) denoting the number of cases.
Each case starts with an integer N (0 < N < 100) that represents the number of nodes in the graph. The next N lines contain N integers each. If the jth(0 based) integer of ith(0 based) line is 1, it means that there is an edge from node i to node j and similarly a 0 means there is no edge.
For each case, output the case number first. Then output 2N+1 lines that summarizes the dominator relationship between every pair of nodes. If node A dominates node B, output 'Y' in cell (A, B), otherwise output 'N'. Cell (A, B) means cell at Ath row and Bth column. Surround the output with |, + and – to make it more legible. Look at the samples for exact format.
Sample Input |
Output for Sample Input |
2 5 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 |
Case 1: +---------+ |Y|Y|Y|Y|Y| +---------+ |N|Y|N|N|N| +---------+ |N|N|Y|N|N| +---------+ |N|N|N|Y|Y| +---------+ |N|N|N|N|Y| +---------+ Case 2: +-+ |Y| +-+ |
Problem Setter: Sohel Hafiz, Special Thanks: Kazi Rakibul Hossain, Jane Alam Jan