11902 - Dominator
Moderator: Board moderators
11902 - Dominator
Thanks i get it now.....AC
Last edited by tanmoy on Tue Jan 11, 2011 10:32 am, edited 1 time in total.
Re: 11902
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
thx for your attention ; ) ![:wink:](./images/smilies/icon_wink.gif)
![:wink:](./images/smilies/icon_wink.gif)
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...
![:wink:](./images/smilies/icon_wink.gif)
Last edited by suneast on Tue Jan 11, 2011 5:40 am, edited 1 time in total.
Re: 11902 - dominator
Finally got Ac
the graph can be disconnected actually
happy coding....![:D](./images/smilies/icon_biggrin.gif)
![:wink:](./images/smilies/icon_wink.gif)
the graph can be disconnected actually
![:)](./images/smilies/icon_smile.gif)
happy coding....
![:D](./images/smilies/icon_biggrin.gif)
Re: 11902 - dominator
I am getting WA.
Can anyone give me some i/o?? Thanks in advance. ![:)](./images/smilies/icon_smile.gif)
![:(](./images/smilies/icon_frown.gif)
![:)](./images/smilies/icon_smile.gif)
Re: 11902 - dominator
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|
+-------------------+
Re: 11902 - dominator
@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.
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 11902 - dominator
The Graph can be disconnected. Thats the trap that caused wa for many teams during contest.
UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 11902 - dominator
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
Last edited by Mehadi on Sun Aug 07, 2011 8:51 am, edited 1 time in total.
-
- New poster
- Posts: 9
- Joined: Mon Aug 13, 2007 7:45 am
Re: 11902 - dominator
Thanks to Mehadi, your WA code active me write AC code.
But I still don't know what bugs in your WA code.
But I still don't know what bugs in your WA code.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11902 - dominator
Input:AC output:
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
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|
+-----------------------+
Check input and AC output for thousands of problems on uDebug!
Time limit exceed: 11902 - dominator
Code: Select all
Accepted
Last edited by raj on Sun Jun 22, 2014 11:20 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11902 - dominator
I solved it running DFS N + 1 times, you're running DFS N * N - 1 times.
Check input and AC output for thousands of problems on uDebug!
Question: 11902 - dominator
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?
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?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11902 - dominator
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.
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.
Check input and AC output for thousands of problems on uDebug!