abhishekmittal964's blog

By abhishekmittal964, history, 3 years ago, In English

Problem Link: https://codeforces.com/contest/1133/problem/F2 My solution link: https://codeforces.com/contest/1133/submission/86270566

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 ?

Full text and comments »