Page 2 of 3
Some test cases!
Posted: Sun Sep 03, 2006 10:27 am
by ivan.cu
Some one can give me test cases such not work for the greedy algorithm:
Code: Select all
1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.
if exist unvisited street print -1
else print guards
Some help please!!!
ivan
Posted: Sun Sep 03, 2006 12:38 pm
by FAQ
Thanks for sclo and Martin Macko, I got AC at last !!
Posted: Sun Sep 03, 2006 2:13 pm
by vinay
me too... Thanks to martin and kp...
bipartite
Posted: Sun Sep 03, 2006 2:17 pm
by vinay
By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long..
please someone forward it if possible
I have an idea and a WA
Posted: Sun Sep 03, 2006 4:49 pm
by hector-chang
Hello!
Based in the following observations I thinked the next solution.
Observation: Once you put a guard in some vertex there is only one admisible configuration of guards for the rest of the connected componet of the graph to which this vertex belongs (One can see this by a BFS starting in this vertex, taking care to guard all the edges). Since every edge must be guarded and there are only two possibilities to guard a particular edge there are at most two admisible configuration of guards for each connected component.
Solution: The problem is now reduced to each connected component and there are at most two numbers to calculate in every one. With a BFS it can be traversed the connected components and then calculated the numbers that I mention.
This program can solve the test cases from this forum and from the original problem in a correct way. However I have WA.
There is a flaw in this algorithm? If anybody wants to see the code I could send it
correct algo
Posted: Sun Sep 03, 2006 4:59 pm
by vinay
The algo is correct...
for each connected component find the minimum no. of guards...
return the sum of all guards of all components...
Check this I/O :
mentioned earlier..
the answer is
Similar I/O are given in the same thread try them out
Re: bipartite
Posted: Sun Sep 03, 2006 5:00 pm
by vinay
vinay wrote:By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long..
please someone forward it if possible
can anyone give some links please
Re: correct algo
Posted: Sun Sep 03, 2006 5:09 pm
by hector-chang
vinay wrote:The algo is correct...
for each connected component find the minimum no. of guards...
return the sum of all guards of all components...
Check this I/O :
mentioned earlier..
the answer is
Similar I/O are given in the same thread try them out
Thanks. But the output is correct, it gives me 1
Posted: Sun Sep 03, 2006 7:31 pm
by mohiul alam prince
Try this Input
Input
Output
Thanks
MAP
Posted: Sun Sep 03, 2006 7:39 pm
by hector-chang
Also correct.
Thanks
Re: Some test cases!
Posted: Mon Sep 04, 2006 12:50 am
by ivan.cu
Help please!!!
Some one can give me test cases such not work for the following greedy algorithm:
Code: Select all
1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.
if exist unvisited street print -1
else print guards
Thank in advance
ivan
Re: Some test cases!
Posted: Mon Sep 04, 2006 1:39 am
by sclo
ivan.cu wrote:Help please!!!
Some one can give me test cases such not work for the following greedy algorithm:
Code: Select all
1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.
if exist unvisited street print -1
else print guards
Thank in advance
ivan
It fails for certain types of graphs that are almost regular, because on some graphs, more than one node will have max degree.
consider this:
Code: Select all
10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 0
Probably your algorithm will visit 0 first, then delete edges, but there are now many nodes with max degree 2, you don't know which one to pick.
If you pick any odd numbered nodes, your algorithm will output wrong answer. The way to fix it is to fix your step 4. Instead of picking any node with largest degree to visit, why don't you just put a guard on a unvisited node adjacent to a neighbor of the node where you have already put a guard.
Posted: Mon Sep 04, 2006 2:28 am
by bafu
Dear ivan, here is the example which will prove the greedy algorithm is wrong:
Code: Select all
input:
1
13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12
output:
4
If you use the greedy algorithm, the output will be 9
Thank!!
Posted: Mon Sep 04, 2006 5:01 am
by ivan.cu
Thank, i can see now that greedy no solve it.
Re: bipartite
Posted: Thu Sep 07, 2006 2:06 pm
by Martin Macko
vinay wrote:vinay wrote:By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long..
please someone forward it if possible
can anyone give some links please
You can google it yourself... try to start with
http://www.google.com/search?q=bipartit ... algorithms.