In the Cherries Mesh problem, what logic is to applied?
I wrote this code but i am not sure in which test cases it’s giving wrong ans, is the soln right?
int main(){
ios_base::sync_with_stdio(false) ; cin.tie(nullptr) ;
int t ;
cin>>t ;
while(t–){
int ans= 0;
int n,m,ci,di ;
cin>>n>>m ;
for(int i=0;i<m;i++){
cin>>ci>>di ;
}
int cnt=m ;
int tedge = n-1 ;
cout<<m+(tedge-cnt)*2<<endl ;
}
}
Copy pasting my reply:-
this gave me AC:-
Found all connected components, added the weights of their spanning trees, finally I connected all those components using red edges.
AC code:-Attempt 2 - Google Docs
bro, i also thought to use a graph and connected components, but can u analyse my solution, just take a glimpse, and sort out anything from it it will be helpful 
Answer is not very correct because your code didn’t count the number of connected components. Thats my conclusion. Only Graph/DSU can solve this problem.
I used to the fact that for V vertices, we need V-1 edges, counted all the Black edges first and then added the remaining red edges
can u provide some tricky testcases for the same
We should discuss that in DM as it deviates from the topic.(I don’t want anyone to bash both of us.)
I figured dfs would time out looking at the constraints since dfs takes {O(|E|+|V|)} and in worst case may take {O(|V|^2)}. Hence, I used DSU. How is that your solution was able to pass the given constraints?
Because my solution’s time complexity is :- Time Complexity of DFS.(I didn’t actually calculate spanning trees as there was no need, only observation was enough for me to calculate each spanning tree, my bad, I never studied DSU.)
Well, you can do dfs on any graph which has (10^5) number of nodes, and (10^5) edges…I don’t think there is anything new in it . No one gets TLE for dfs for sparse graphs. And worst case for DFS is :- O(V+E).
I repeat, WORST CASE FOR DFS IS :- O(V+E) .
But wait. What happens if {|E|=\dfrac{|V|*|V-1|}{2}}. Won’t it be {O(|V|^2)}?
Now, its frustrating for me. Who said the number of edges is always ‘v*(v-1)/2’??? This is the condition only for a complete graph. My graph has only ‘M’ edges , mentioned in the problem statement itself. In short, my graph has 10^5 nodes and 10^5 edges.(All edges in my graph are BLACK.) . I won’t give further clarifications.
what there will be only 1e5 edges so dfs will never go beyond 2*1e5 in worst case …dfs is the optimal solution here /////
karan what about third question can u help me with a littile bit–
here is my solution : CBxHy1 - Online C++0x Compiler & Debugging Tool - Ideone.com
How can i optimise my solution, correct me if i m wrong
DSU is only useful for trees not for graph…
this passes small test cases??
yes,it passes small test cases
Damn. I saw only {M \leq N*(N-1)/2} and didn’t see {0 \leq M \leq 10^5} which is given at the end. Did I just get 3 penalties for not seeing this. My first attempt with dfs passed all testcases. And to optimize it I used DSU.
Kickstart considers last successfully submitted solution as final solution?
And thank you @anon55659401 for pointing it out
3rd one was sad event. As my brute-force didn’t pass anything. 2nd problem is standard Gaussian+Diophantine.
