Beautiful vertices

#1


can you plz tell what is wrong with my code

1 Like
#2

Hello @Dhruv-Miglani-2090236747707980

You considered a vertex as beautiful if that vertex has more number of children than it has number of parents. But why you incremented “p” only when parent[node] != 0. Even a master vertex can be beautiful.

Also the statement “A vertex is called beautiful if it has more children than its parent” can have other meaning i.e., a vertex is beautiful if it has more number number of children than its parent vertices have.
Modify your code according to this situation too and check if it works this way, if NOT reply to this thread and I will help you out.

#3


still answer is incorrect.

#4

Can you please provide the solution? I didn’t get it.

#5

Hello @Dhruv-Miglani-2090236747707980 @hetp111

The edges that are provided in this question are NOT the final edges.
Example:-
7 5
2 1
3 1
4 3
6 5
6 7

Here in this input we can see that there are 2 connected components.
In the first connected component {1, 2, 3}, 1 is the master vertex (“In any connected component of the graph, vertex with the lowest value in that component serves as the master parent” given in the question) so there are no incoming edges on vertex 1 but only outgoing edges.
So edge 2 1 is like 1->2, edge 3 1 is like 1->3, and egde 4 3 is like 3->4

Similarly in the second component {5, 6, 7}, 5 is the master vertex and edge 6 5 is assigned direction 5->6 and edge 6 7 is 6->7.

To find the directions assigned to each edge, we start from the master vertex and for each connective edge i
we push realList[MasterVertex].push_back(i) to the real list, then we do the same for their children.

The code

Here I have used the set to find the master vertex of each component.

#6

even your code isnt getting submitted . Check out on cb ide along with test cases.

#7

Hello @Dhruv-Miglani-2090236747707980 @hetp111

There was just an array which was NOT used anywhere, so codingblocks ide was producing an error.
You should have read the code and checked for the compilation issue.

The modified code

#8

thanks for the code but it would have been better if you could have editted my own code instead of providing me with another code.

#9

Hello @Dhruv-Miglani-2090236747707980

How could I have edited your code. You approach to solve this problem is different than mine.

#10

This is exactly what i am saying you have a different approach and as guide to me you should have told me where my approach went wrong instead of giving me another approach.for another approach i would have just googled this queation and would have got 100 other approaches

#11

What you considered in your approach is that a vertex is beautiful if the number of children is greater than the number of parents while I told you that the statement “A vertex is called beautiful if it has more children than its parent” can have other meaning i.e., a vertex can be beautiful if it has more number of children than the number of children its parent vertices have and this is the approach that I used to solve the problem.
I explained the code above too.

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#13

hey how can u say that 5 is the master vertex ?? 5 is connected with both 6,7 and it is also not given that it is unidirectional ?? how then ??

#14

what was ur logic for this prob ?? and how were u able to find master vertex

#15

@thapacyrus29
Our second component is {5, 6, 7} and it is mentioned in the question that the master vertex is the one with the lowest value. Hence 5 is the master vertex

1 Like
#16

I see thanks !! But what was ur logic to find Mvertex ??

#17

@thapacyrus29

First you find all the connected components in the graph.
Then for each connected component, the vertex with the lowest value inside that connected component serves as the master vertex.

#18

Finally found a really Awesome Explanation of this question. Do check it out.
video link:-

#19

Finally found a really good explanation of this question. Do check it out