Page 1 of 2

11902 - Dominator

Posted: Mon Jan 10, 2011 1:39 pm
by tanmoy
Thanks i get it now.....AC

Re: 11902

Posted: Mon Jan 10, 2011 2:27 pm
by MRH
try this case
1
4
1 1 0 1
1 0 1 1
1 1 1 1
1 1 0 1
acc output
Case 1:
+-------+
|Y|Y|Y|Y|
+-------+
|N|Y|Y|N|
+-------+
|N|N|Y|N|
+-------+
|N|N|N|Y|
+-------+

Re: 11902

Posted: Tue Jan 11, 2011 5:33 am
by suneast
Hi, MRH :wink:

My code have passed your data post above, but I still keep getting WA... and don't know why

My algorithm is quite simple:
delete NODE_U from the graph
if I can't visit NODE_V from 0, then NODE_U is Dominator of NODE_V

and here's my main algorithm code

Code: Select all

deleted... after got ac...
thx for your attention ; ) :wink:

Re: 11902 - dominator

Posted: Tue Jan 11, 2011 5:39 am
by suneast
Finally got Ac :wink:

the graph can be disconnected actually :)

happy coding.... :D

Re: 11902 - dominator

Posted: Tue Jan 11, 2011 6:46 pm
by Rashad
I am getting WA. :( Can anyone give me some i/o?? Thanks in advance. :)

Re: 11902 - dominator

Posted: Tue Jan 11, 2011 9:20 pm
by tanmoy

Code: Select all

4
5
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
0 0 0 0 0
1 1 0 0 1
Case 1:
+---------+
|Y|Y|N|N|Y|
+---------+
|N|Y|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|Y|N|N|Y|
+---------+
10
1 0 0 0 0 1 0 1 0 1
1 0 0 1 0 0 1 1 0 1
0 0 0 1 1 1 1 0 1 0
0 0 0 1 0 0 0 0 1 0
0 1 1 1 1 1 0 1 1 0
0 0 1 0 1 1 1 1 1 0
0 0 1 1 1 0 1 1 1 0
0 1 1 1 0 0 0 1 0 0
1 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 1 1
Case 2:
+-------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
|N|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|Y|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|Y|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|Y|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|Y|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|Y|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|Y|
+-------------------+
10
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 1 0 0 0
1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 0 1 1 1 0
1 1 1 0 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 1 0 1 1 1
Case 3:
+-------------------+
|Y|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
10
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Case 4:
+-------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
|N|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|Y|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|Y|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|Y|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|Y|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|Y|N|
+-------------------+
|N|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
try those cases....

Re: 11902 - dominator

Posted: Tue Jan 11, 2011 11:29 pm
by crip121
@tanmoy, i think all of the graph in your i/o is not DAG. but strangly, in problem statement, 2nd graph contains a self loop. although i treated given graph as a DAG and got AC.

Re: 11902 - dominator

Posted: Thu Jan 13, 2011 2:50 pm
by Shafaet_du
The Graph can be disconnected. Thats the trap that caused wa for many teams during contest.

Re: 11902 - dominator

Posted: Sun Jan 23, 2011 7:50 am
by Mehadi
WA
My code passed all input given in this thread.But still WA.Can anyone plz help me.It also works for disconnected graph

Code: Select all

Removed after Acc

Re: 11902 - dominator

Posted: Sun Jan 30, 2011 1:55 pm
by pfiesteria
Thanks to Mehadi, your WA code active me write AC code.
But I still don't know what bugs in your WA code.

Re: 11902 - dominator

Posted: Mon Mar 04, 2013 10:58 pm
by brianfry713
Input:

Code: Select all

1
12
1 1 1 0 0 1 1 1 1 0 0 0
0 0 1 0 1 0 0 1 1 1 0 1
0 0 1 1 0 1 1 0 0 1 0 0
0 1 1 0 1 0 0 0 0 1 0 1
1 0 0 1 1 0 0 0 0 1 1 1
1 1 1 1 0 1 0 0 0 1 0 0
1 1 0 1 0 0 0 0 1 1 1 0
1 1 0 0 0 0 1 1 1 0 1 1
1 1 1 1 0 0 1 0 1 1 1 1
0 0 1 1 1 0 1 0 1 0 0 0
0 1 1 1 1 0 0 0 1 1 0 0
1 1 0 0 1 1 0 1 1 1 0 0
AC output:

Code: Select all

Case 1:
+-----------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-----------------------+
|N|Y|N|N|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|Y|N|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|Y|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|Y|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|Y|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|Y|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|Y|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|Y|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|Y|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|N|Y|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|N|N|Y|
+-----------------------+

Time limit exceed: 11902 - dominator

Posted: Sat Oct 19, 2013 9:23 pm
by raj

Code: Select all

Accepted

Re: 11902 - dominator

Posted: Mon Oct 21, 2013 9:50 pm
by brianfry713
I solved it running DFS N + 1 times, you're running DFS N * N - 1 times.

Question: 11902 - dominator

Posted: Mon Jun 09, 2014 7:33 pm
by raj
I have a question here
if the 0th node is the start node then if the graph is disconnected then is it will be all the connected components of the graph 1st random node is the start node?

Re: 11902 - dominator

Posted: Thu Jun 12, 2014 9:32 pm
by brianfry713
I can't understand your question.
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.