skpro19's blog

Optimisation needed for a dfs problem
By skpro19, history, 7 years ago, In English

I am getting a TLE on this problem using DFS. This is my submission. Can someone suggest some optimizations?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use BFS. Or simple std::sort d[] array ).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But why am I getting a TLE in my approach?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 7   Vote: I like it 0 Vote: I do not like it 
      for (int i = 1; i <= k - 1 + (curr == start); i++) {
		if ((int)mpp[len].size()) {

            int last = mpp[len].back();
            mpp[len].pop_back();
			ans.pb({ curr, last });
			len++;
			dfs(last);
			len--;
			//mpp[len].pop_back();

		}else break;// <<<<-------------SEE
	}
      → Reply