Logic Checking Beautiful Vertices

#1

Here is my understanding of the question:

  1. The graph may contain more than 1 connected component.
  2. In every connected component there is a node/vertex with lowest value, this vertex is master vertex/parent in the CC. Eg a connected component contains vertices 3,4,5,1 so 1 will be the master parent of this CC, and this vertex will not have any parent.
  3. Given this info, i do the following:
    3a. I start the loop from 1 till n, this is to start dfs and get components from master vertex. i.e vertex with lowest value.
    3b. I maintain a connect component vector which stores vertices in that connected component.
    3c. After getting parent and children of every vertex using DFS in the current CC, i check the condition that if parent of current node has more children than the current node then i increase the counter by 1. i.e i have found 1 beautiful vertex.

Please tell me where am i going wrong:

My Code:

@apaarkamal
@Saurabh-Kumar-1331476656958199

#2

Q link please unable to find the Q.

#3

Coudnt find the question:

BEAUTIFUL VERTICES
You are given a graph with N vertices and M edges. Master parent is the vertex which has no parent but may have 0 or more children. In any connected component of the graph, vertex with the lowest value in that component serves as the master parent. A vertex is called beautiful if it has more children than its parent. Count the number of beautiful vertices in the given graph. The graph has no cycles or self loops.

Input Format:
First line consists of two space separated integers denoting N and M and the following M lines consist of two space separated integers X and Y denoting there is an edge between vertices X and Y.

Constraints:
1 <= N <= 100000 0 <= M <= N-1 1 <= x,y <= N

Output Format
Print the number of beautiful vertices in the graph.

Sample Input
4 3
1 2
2 3
2 4
Sample Output
1

#4

my thought process.
suppose we have n vectors containing n connected graphs.
no of beautiful vertices in a connected component will be number of vertex having degree more than 2 plus one( if master node degree <=2 ). Tell me if you find any mistake in this approach…

#5

if dont think there is any further need to do dfs after getting connected component.

#6

I am not able to understand your approach also can you provide the code for what you are saying.
@Saurabh-Kumar-1331476656958199

#7