The link to the problem is here.

The problem asks for edit step ladders. An edit step ladder is a sequence of transformations where edit distance is of 1 and the words are in lexicographically increasing order. Based on the ideas in the onlinejudge board, I implemented a solution. First generate an undirected graph where each edge implies a valid transformation/edit step. Then use DFS to find the maximum depth. But I'm getting wrong answer on the following test case.

aaaaaa
aaaaaaa
aaaaaah
aaaaah
aaaah
aaah
aaarg
aaarge
aaarh
aabrge
aacrd
aacre
aaraah
aard
araah
ard
arde
arded
ardev
raah
rdev
vaah
vaahb
vaahe

The answer is supposed to be 11. But my code currently returns 8. The code is as follows. The only different step that I am doing is adding a $ at the end. This is done to save me from writing two loops. I have one loop where I add characters before the current character and by having a dummy character of dollar sign it will work for adding the character at the end of the string too. I have done some checking with a separate edit step program and it seems that the generated graph is correct. I am most probably making a mistake in the DFS part. Specifically, this line

if (!discovered[y] and ind_to_str[v] < ind_to_str[y])

Any help with this is appreciated.

#include <bits/stdc++.h>
#define MAX (25000 + 2)

using namespace std;

int max_depth = 0;
int dtime = 0;
vector<unordered_set<int>> graph;
vector<string> words;
unordered_map<string, int> str_to_ind;
unordered_map<int, string> ind_to_str;
vector<int> cur_chain, best_chain;

int parent[MAX];
int discovered[MAX];
int processed[MAX];
int entry_time[MAX];
int exit_time[MAX];

void dfs(int v, int d) {
  cout << "At " << ind_to_str[v] << " with depth " << d << endl;
  // max_depth = max(max_depth, d);
  cur_chain.push_back(v);
  if (d > max_depth) {
    max_depth = d;
    best_chain = cur_chain;
  }
  discovered[v] = true;
  entry_time[v] = ++dtime;

  for (int y : graph[v]) {
    if (!discovered[y] and ind_to_str[v] < ind_to_str[y]) {
    // if (!discovered[y]) {
      parent[y] = v;
      dfs(y, d + 1);
    }
  }

  exit_time[v] = ++dtime;
  processed[v] = true;
  cur_chain.pop_back();
}

void init_search() {
  for (int i = 0; i < MAX; ++i) {
    parent[i] = entry_time[i] = exit_time[i] = -1;
    discovered[i] = processed[i] = false;
  }
  dtime = 0;
}

int main(void) {
  string line;
  int ind = 0;
  while (getline(cin, line) and line.length() > 0) {
    // append an extra dollar so that you don't have to
    // have an extra loop at the end for adding characters
    // at the end of a string, you can have one loop which
    // adds characters before every character and you've
    // added characters in all places
    line += "$";
    words.push_back(line);
    str_to_ind[line] = ind;
    ind_to_str[ind++] = line;
  }
  int n = words.size();
  
  graph.assign(n, unordered_set<int>());

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < words[i].length() - 1; ++j) {
      for (char c = 'a'; c <= 'z'; ++c) {
        // insert
        string added = words[i].substr(0, j) + string(1, c) + words[i].substr(j + 1, string::npos);
        if (str_to_ind.count(added) != 0) {
          int cur_ind = str_to_ind[words[i]];
          int next_ind = str_to_ind[added];
          if (cur_ind == next_ind) continue;
          
          graph[cur_ind].insert(next_ind);
          graph[next_ind].insert(cur_ind);
        }

        // replace
        string changed = words[i];
        changed[j] = c;
        if (str_to_ind.count(changed) != 0) {
          int cur_ind = str_to_ind[words[i]];
          int next_ind = str_to_ind[changed];
          if (cur_ind == next_ind) continue;

          graph[cur_ind].insert(next_ind);
          graph[next_ind].insert(cur_ind);
        }
      }

      // delete
      string deleted = words[i].substr(0, j) + words[i].substr(j + 1, string::npos);
      if (str_to_ind.count(deleted) != 0) {
        int cur_ind = str_to_ind[words[i]];
        int next_ind = str_to_ind[deleted];
        if (cur_ind == next_ind) continue;

        graph[cur_ind].insert(next_ind);
        graph[next_ind].insert(cur_ind);
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    cout << ind_to_str[i] << ": ";
    for (int x : graph[i]) {
      cout << ind_to_str[x] << " ";
    }
    printf("\n");
  }

  for (int i = 0; i < n; ++i) {
    cur_chain.clear();
    init_search();
    cout << "Starting with " << ind_to_str[i] << endl;
    dfs(i, 1);
  }

  printf("%d\n", max_depth);
  for (int i = 0; i < best_chain.size(); ++i) {
    cout << ind_to_str[best_chain[i]] << endl;
  }
  
  return 0;
}