How to remove TLE

#1

Question ----https://assessment.hackerearth.com/challenges/hiring/buyhatke-hiring-challenge/algorithm/maximal-connection/
My Code
https://ide.codingblocks.com/s/313591

#2

@Bhawna,

for(ll p=0;p<n;p++)
	{
		unsigned ll co=0;
		for(ll k=0;k<m_;k++)
		{
			if(G.find(special_indices[k])==G.find(p))
			{
				co++;
			}
		}
		sum+=co;
	}

You are using nested loops which make the complexity to be O(n*m). You should try to use some maths to reduce the complexity to linear.

#3

I know this but I am not getting how to make it linear that’s why I asked here

#4

@Bhawna,
Code link Here.
I have used dsu and pre calculated number of special nodes in each connected component. Now final answer is simply sum of number of special nodes in connected component of each node.

#5

I Got AC …

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.