Help needed in Spanning Tree with 1 fixed degree

Revision en1, by abhishekmittal964, 2020-07-08 15:03:19

Problem Link: My solution link:

I dont understand why this solution is exceeding memory limit on testcase 10. Logic: A few neighbours of node 1 may be connected. Lets say 2,3,4 are connected either directly or indirectly(I want to know if they are connected through some other vertices other than 1). So I assign one of these vertices value 2 and the rest of the vertices(3,4) value 1 and mark them visited. I now go to the next unvisited neighbour of 1 and do the same process. This way i get the minimum number of vertices 1 needs to be connected to, so that a connected tree can be formed(these vertices are those whose value is 2). New degree of 1 d= D-(no. of neighbours of 1 whose value is 2). Now i choose d random neighbours whose value is 1 and add them to my tree. Then i just create a bfs tree from each of the neighbours of 1.

Is there a mistake in the implementation ?


  Rev. Lang. By When Δ Comment
en1 English abhishekmittal964 2020-07-08 15:03:19 1041 Initial revision (published)