## 11902 - Dominator

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Question: 11902 - dominator

ok Sir i got the point and my code is accepted by running DFS n-1 time..
But two things i just want to know

1) i didn't consider self-loop is it ok?

2) suppose, we want to find out is x dominates y?
if y is NOT reachable from the start node(0th) then y does not have any dominator so according to me array[x][y] = YES
but, it gives wrong answer but when i put array[x][y] = NOT in this case it is accepted..

Thanks in advance ...

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 11902 - Dominator

Hi, what is wrong with my solution for this problem, WA at 0.516.

Code: Select all

``````#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> A[110];
bool Visited[110];
bool Reachable[110];
bool Dominator[110][110];
void dfs(int u){
Visited[u]=true;
Reachable[u]=true;
for(int j=0;j<(int)A[u].size();j++){
int v=A[u][j];
if(Visited[v]==false){
dfs(v);
}
}
}
void dfs(int u, int x){
if(u==x) {return;}
Visited[u]=true;

for(int j=0;j<(int)A[u].size();j++){
int v=A[u][j];
if(Visited[v]==false)
dfs(v,x);
}
}
void PrintStars(int N){
printf("+");
for(int i=0;i<2*N-1;i++){
printf("-");
}
printf("+\n");
}
int main(){
//freopen("in.txt","r",stdin);
int TestCases;int Caseno = 0;
scanf("%d",&TestCases);
while(TestCases--){
memset(Visited,false,sizeof Visited);
memset(Reachable,false,sizeof Reachable);
for(int i=0;i<110;i++){
for(int j=0;j<110;j++){
Dominator[i][j]=false;
}
}
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int temp;
scanf("%d",&temp);
if(temp) A[i].push_back(j);
}
}
dfs(0);
for(int x=0;x<N;x++){
if(Reachable[x]==true){
memset(Visited,false,sizeof Visited);
dfs(0,x);
for(int j=0;j<N;j++){
if(Reachable[j]){
if(Visited[j]){
Dominator[x][j]=false;
}
else Dominator[x][j]=true;
}
else Dominator[x][j]=false;
}
}
else{
for(int j=0;j<N;j++) Dominator[x][j]=false;
}
}
printf("Case %d:\n",++Caseno);
for(int i=0;i<N;i++){
PrintStars(N);
for(int j=0;j<N;j++){
printf("|");
if(Dominator[i][j]==true)
printf("Y");
else printf("N");
}
printf("|\n");
}
PrintStars(N);
}
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11902 - Dominator

bradd123, are you clearing A between test cases?
Check input and AC output for thousands of problems on uDebug!

ak8226
New poster
Posts: 1
Joined: Sat Jun 13, 2015 12:36 pm

### Re: 11902 - Dominator

I am getting time limit.Here is my code.It's running for all cases that i have checked.please guide me.

Code: Select all

``````# include <bits/stdc++.h>

using namespace std;

#define WHITE 0
#define BLACK 1
typedef vector<int> edges;
typedef vector<edges> nodes;

int permant[110];
int d_num[110];

void dfs(int node,int parent,int removed,nodes nd)
{
if(node!=removed)
{
d_num[node]=BLACK;

int v;
for (edges::iterator it=(nd[node]).begin();it!=(nd[node]).end(); ++it)
{
v=*it;

if( ( v!=parent ) && (v!=removed) && ( d_num[v]==WHITE ) )
{
dfs(v,node,removed,nd);
}
}
}

}
void decorate(int size)
{
size=2*size-1;
printf("+");
for (int i = 0; i < size; ++i)
{
printf("-");
}
printf("+\n");

}

int main()
{
int tests,size,is_present;
scanf("%d",&tests);
for (int a=0;a<tests;a++)
{
nodes nd;

scanf("%d",&size);

for (int i = 0; i < size; ++i)
{
edges ed;
for (int j = 0; j < size; ++j)
{
scanf("%d",&is_present);
if(is_present==1)
ed.push_back(j);
}
nd.push_back(ed);
}

memset(permant,0,sizeof(permant));
memset(d_num,0,sizeof(d_num));

dfs(0,0,200,nd);

printf("Case %d:\n",a+1);

decorate(size);

for (int i = 0; i < size; ++i)
{

permant[i]=d_num[i];

printf("|");
if(permant[i])
{
printf("Y");
}
else
{
printf("N");
}
}
printf("|\n");

for (int i = 1; i < size; ++i)
{
decorate(size);
memset(d_num,0,sizeof(d_num));
dfs(0,0,i,nd);

for (int j = 0; j < size; ++j)
{
printf("|");
if(d_num[j]==0 && permant[j])
{
printf("Y");
}
else
{
printf("N");
}
}
printf("|\n");
}
decorate(size);
}

}
``````

amrondonp
New poster
Posts: 5
Joined: Fri Apr 03, 2015 2:29 am

### Re: 11902 - Dominator

First of all. Rund DFS from node 0 this will give you all the nodes reachables from 0

then consider n disctinct graph's
let the graph n_i be the same graph g but without the node i

run DFS from 0 in those new graphs

If node J were reachable from 0 in the original graph and were NOT reachable in the graph n_i then, i is Dominates J because if i doesn't exist there is no path from 0 to J. In other words every path from 0 to J goes through i.

Complexity O(T*(n+E)^2) where T is the number of test cases.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11902 - Dominator

Getting TLE for this problem.

Code: Select all

``````Instead of using System.out.println() for each character I made a stringbuilder which holds full output of a case,
then printed that stringbuilder with only one System.out.println(). That is how I got the magical word "Accepted"!!!
``````