OJ Board

Posted: **Mon Jan 10, 2011 1:39 pm**

Thanks i get it now.....AC

Posted: **Mon Jan 10, 2011 2:27 pm**

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

Posted: **Tue Jan 11, 2011 5:33 am**

Hi, MRH

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 ; )

Posted: **Tue Jan 11, 2011 5:39 am**

Finally got Ac

the graph can be disconnected actually

happy coding....

Posted: **Tue Jan 11, 2011 6:46 pm**

I am getting WA.

Can anyone give me some i/o?? Thanks in advance.

Posted: **Tue Jan 11, 2011 9:20 pm**

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

Posted: **Tue Jan 11, 2011 11:29 pm**

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

Posted: **Thu Jan 13, 2011 2:50 pm**

The Graph can be disconnected. Thats the trap that caused wa for many teams during contest.

Posted: **Sun Jan 23, 2011 7:50 am**

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

Posted: **Sun Jan 30, 2011 1:55 pm**

Thanks to Mehadi, your WA code active me write AC code.
But I still don't know what bugs in your WA code.

Posted: **Mon Mar 04, 2013 10:58 pm**

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

Posted: **Sat Oct 19, 2013 9:23 pm**

Code: Select all

Accepted

Posted: **Mon Oct 21, 2013 9:50 pm**

I solved it running DFS N + 1 times, you're running DFS N * N - 1 times.

Posted: **Mon Jun 09, 2014 7:33 pm**

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?

Posted: **Thu Jun 12, 2014 9:32 pm**

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.

OJ Board

11902 - Dominator

11902 - Dominator

Re: 11902

Re: 11902

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Re: 11902 - dominator

Time limit exceed: 11902 - dominator

Re: 11902 - dominator

Question: 11902 - dominator

Re: 11902 - dominator