Silly me, if two nodes belong to different components then also their value will be true in array and we cant add that edge.
Although this works in Prim's.
Why can't we just use a boolean array to keep track of the vertices that are a part of any component. That will be sufficient to check if an edge can be added or not ?
Strange, I used C language and as I read in the comments that WA case, I did that workaround.
Still I was getting 60/100.
Then after a day I tried to increase the size of the matrix from 75 to 100, I got 80.
Then i increased the size to 250, I got it accepted (100/100).
The constraint on N was wrong too ?
Himanshu's Hints are the best, but they took me a lot of time to understand so here I'm elaborating the stuff that would help to understand those hints easily.
Here's my code if u don't understand above stuff after a lot of thinking.
I have implemented my own heap.
I meant that suppose, my last transaction was buying, and i bought it on 1st day and when I'm recursing and on some later day if we sell and we realise that the dp table value for selling on that day is available and we use it. But what if that selling value was for selling an item bought on day 2..... Or any other day except day 1. Then that value is incorrect to use for day 1 right. So we will have to keep track of the day on which we last bought too.
Ok, but what i was thinking is: that once we have recursed through a day with say x transactions. Then, if we recurse through it again the dp array would already have the answer, so we would just take it. But what if dp array value that got returned as it was available was from another day that we last bought on rather than the current last day we bought on.
Than that would be wrong, would'nt it. So wouldnt it need a 3D matrix also saving the day we previously bought on.