uva 11902 - Dominator

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 0^th 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.

Input

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 j^th(0 based) integer of i^th(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.

Output

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 atA^th row and B^th 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

Graph Traversal, graph theory(reference)

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int R,cases=1;
vector<int>egs[100],node;
bool trav[100],dom[100][100],rec[100];
void DT(int cur,int nop){
    int b;
    if(DBG)printf("cur %d ",cur);
    trav[cur]=1;
    rep(i,egs[cur].size()){
        b=egs[cur][i];
        if(b==nop)continue;
        if(!trav[b])DT(b,nop);
    }
}
void DFS(int cur){
    int b;
    trav[cur]=1;
    node.push_back(cur);
    rep(i,egs[cur].size()){
        b=egs[cur][i];
        if(!trav[b])DFS(b);
    }
}
void print(){
    printf("child(%d): ",node.size());
    rep(i,node.size())printf("%d ",node[i]);
}
void ans(){
    int b;
    node.clear();
    memset(trav,0,sizeof(trav));
    memset(dom,0,sizeof(dom));
    DFS(0);if(DBG)print();
    memcpy(rec,trav,sizeof(trav));
    rep(i,R)if(trav[i])dom[0][i]=1;
    REP(i,1,node.size()){
        b=node[i],memset(trav,0,sizeof(trav));
        DT(0,b);
        rep(j,R)if(rec[j]&&!trav[j])dom[b][j]=1;
    }       
    printf("Case %d:\n",cases++);
    printf("+");rep(i,R)if(i==0)printf("-");else printf("--");printf("+\n");
    rep(i,R){
        printf("|");
        rep(j,R){if(dom[i][j])printf("Y");else printf("N");printf("|");}
        printf("\n");
        printf("+");rep(i,R)if(i==0)printf("-");else printf("--");printf("+\n");
    }
}
int main(){
    int n,a;
    scanf("%d",&n);
    rep(i,n){
        scanf("%d",&R);
        rep(i,100)egs[i].clear();
        rep(i,R)rep(j,R){scanf("%d",&a);if(a)egs[i].push_back(j);}
        ans();
    }
}