i was solving this(http://www.spoj.pl/problems/LEGO/) problem in spoj..i tried it using disjoint set DS bt i m getting TLE..
wat i did was for each pair(total of n(n-1)/2 pairs) i checked whether they r connected or not ..if they are connected and their sets r different then i did a union operation for those pairs..
( total no. of sets in starting - total union operations ) gives me the num. of disconnected components..
is there any other method so tht i can avoid TLE(other thn building a graph and doing DFS to find out the no. of disconnected components)..
here is my code tht was TLEed..any optimization tht i can do in it???
thnx in advance fr ur reply..
wat i did was for each pair(total of n(n-1)/2 pairs) i checked whether they r connected or not ..if they are connected and their sets r different then i did a union operation for those pairs..
( total no. of sets in starting - total union operations ) gives me the num. of disconnected components..
is there any other method so tht i can avoid TLE(other thn building a graph and doing DFS to find out the no. of disconnected components)..
here is my code tht was TLEed..any optimization tht i can do in it???
thnx in advance fr ur reply..
The time limit should be at least 10 minutes for your program to pass. I didn't watch the source code though. Try to find another algorithm, that is my advice.