_invincible_'s blog

Need Help in SPOJ Problem(Maximum Spanning Tree)
By _invincible_, history, 4 years ago, In English

Problem-MARYBMW

**My Approach:- ** At first,I've created a maximum spanning tree from the given data using kruskal algorithmn, Again , i had found the shortest path from 1 to n and take the minimum edge weight which would be our ans as obvious. Everthing worked fine but getting Time Limit Exceeded(TLE). Please correct me if I am wrong in any of my approach

Link to My Code

Need Help..I am getting TLE on test 15 and can't figure out how can I make it faster. Any help would be appreciated.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by _invincible_ (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by _invincible_ (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Your disjoint set doesn't have either path compression, or union by rank/size. So each find/union operation can take O(n).

Try: return parent[x] = find_set(parent[x],parent);

→ Reply