codeworrior's blog

spoj problem
By codeworrior, 14 years ago, In English
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..
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Most definitely you need another algo. N can be as big as 100000 (105). And your algo is at least N2
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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You can't just iterate through all pairs of blocks. There are too many of them. Think how to only merge those blocks that are connected to each other. You can refer to my solution for example.
→ Reply