11902 - Dominator

[raj]

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 ...

[bradd123]

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]

bradd123, are you clearing A between test cases?

[ak8226]

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]

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.

That's it. Hope it'll help you.

[Mukit Chowdhury]

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"!!!