I was looking into this question: SPOJ.com - Problem PT07X
I’m using the following algorithm: Ubuntu Pastebin
But this is failing for the below condition:
6
1 2
2 3
3 4
4 5
5 6
Output: 3
Correct Solution: 2
Am i missing something?
Edited
I was looking into this question: SPOJ.com - Problem PT07X
I’m using the following algorithm: Ubuntu Pastebin
But this is failing for the below condition:
6
1 2
2 3
3 4
4 5
5 6
Output: 3
Correct Solution: 2
Am i missing something?
Edited
why have u written 5 edges and 5 nodes in the input ?
Sorry, that’s *6
6
1 2
2 3
3 4
4 5
5 6
Then correct output should be 3 because for 6 nodes you can see the image for one of the optimal solutions
Now for your solution I made some changes and also commented the logic also and it gave AC . Hope u understand them , if not then feel free to ask
Thanks for you reply!
In the above graph, if you select 2 and 5 as the nodes, every other node will have an edge connecting to the selected nodes. Hence minimum vertex would be 2, right?
For the case:
6
1 2
2 3
3 4
4 5
5 6
It is giving 3 as output but 2 is the correct solution.
if u select 2 and 5 as MVC then the edge connecting 3 and 4 would not be belonging to any selected vertex
Correct. But I need the nodes that connects to every other node. Correct me if I got it wrong with MVC. I’m trying to figure out a use case where I need to find the nodes that are connected to every other node through an edge.
For example, in the graph you posted, if I select 2 and 5, all my other nodes (1,3,4,6) are connected to 2 and 5.
That’s MVC right? So in my case (which is different from the question I posted), I need the minimum number of nodes directly connecting all other nodes in an undirected graph. I guess I mistook it for MVC.
My actual question is to find the minimum number of nodes directly connecting all other nodes in an undirected graph while MVC says that all edges has atleast one end point in subset.
Its 3 only
That’s for MVC, but i have a different question.