SRM 705, D2, 500-Pointer (AlphabetOrderDiv2)

James S. Plank

Fri Feb 3 15:30:41 EST 2017
I have three letters for you: DFS.

Although Topcoder calls this a sorting problem, I think it is much easier to view as a graph problem: Turn the words into a directed graph. There are 26 nodes, corresponding to the 26 letters of the alphabet. For each pair of adjacent characters i and j in a word, if i does not equal j, then put an edge from node i to node j.

Then, use DFS to perform cycle detection on each node. If you find a cycle, then it is "Impossible." If you don't, find a cycle on any node, then return "Possible."

The DFS here is a little more tricky than on an undirected graph. On an undirected graph, all you need is a visited array, which is a boolean. See the section entitled "Depth First Search To Perform Cycle Detection", from the DFS lecture notes from CS302 for a nice example.

In a directed graph, it's a little trickier. The reason is that in an undirected graph, if there is a path from A to B, then there is a path from B to A. That is not true in a directed graph.

What I do to handle the directed graph is make visited an integer, which can hold one of three values:

This allows you do perform the DFS for cycle detection efficiently. Let me give you an example with pictures. Suppose that the two words are "cat" and "cot". This will give you the following graph:

You'll note that this graph has no cycles. Were it undirected, it would have a cycle. Now, suppose you run through the letters in order to detect cycles. You start with 'a'. When you call DFS on it, you set visited to one, and you will then call DFS on 't':

This will set t's visited field to one, and since there are no outgoing edges, the DFS will complete instantly. There is no cycle with 't', so you set its visited field to two, and return to 'a':

Now, 'a' is done. You set its visited field to two, and the DFS returns that there is no cycle with 'a'. Here's the state of the graph:

Next, you call DFS on 'c'. This sets its visited field to one, and calls DFS on 'a'. Since 'a' has completed its DFS, you return instantly that there is no cycle with 'a'. Here's the state of the graph:

Next, you process the edges from 'c' to 'o', and call DFS on 'o'. This will set o's visited field to one, and it will call DFS on 't':

Since 't' has completed its DFS, you return instantly that there is no cycle with 't'. Now, 'o' can return that there is no cycle, as can 'c':

You will call DFS on 'o' and 't' next, but they are already done. Now, you're done and can return "Possible", because there are no cycles in the graph.


My Solution

I'm putting my solution below. I store the graph using an adjacency matrix, and I print out the adjacency matrix before doing the DFS's. For example, here's the adjacency matrix for example 0:
  abcdefghijklmnopqrstuvwxyz
a 00000000000000000001000000
b 00000000000000000000000000
c 00000001000000000000000000
d 00000000000000000000000000
e 00000000000000000000000000
f 00000000000000000000000000
g 00000000000100000000000000
h 00000000000000000000000000
i 00000000000001000000000000
j 00000000000000000000000000
k 00000000000000000000000000
l 00001000000000000000000000
m 10000000000000000000000000
n 00010010000000000000000000
o 00000000000000000000100000
p 00000000000000000000000000
q 00000000000000000000000000
r 00000000000000100000000000
s 00000000100000000000000000
t 00100000000000000000000000
u 00000000000001000000000000
v 00000000000000000000000000
w 00000000000000000000000000
x 00000000000000000000000000
y 00000000000000000000000000
z 00000000000000000000000000
And here's the commented code (in Solution.cpp):

/* Topcoder SRM 705, D2 500-Pointer.
   AlphabetOrderDiv2
   James S. Plank
   Fri Feb  3 16:23:38 EST 2017
 */

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;


class AlphabetOrderDiv2 {
  public:
    vector < vector <int> > Adj;
    vector <int> Visited;
    string isOrdered(vector <string> words);
    int DFS(int n);
};

int AlphabetOrderDiv2::DFS(int n)
{
  int i;

  if (Visited[n] == 2) return 0;   /* When visited == 2, we already know there's no cycle. */
  if (Visited[n] == 1) return 1;   /* However, if visited == 1, we've discovered a cycle. */

  Visited[n] = 1;

  /* Call DFS(i) on every node where there is an edge from n to i. 
     Return instantly if you've detected a cycle. */

  for (i = 0; i < Adj[n].size(); i++) {
    if (Adj[n][i]) {
      if (DFS(i)) return 1;
    }
  }

  /* If there's no cycle, you can set visited to 2, and return that there is no cycle. */

  Visited[n] = 2;
  return 0;
}

string AlphabetOrderDiv2::isOrdered(vector <string> words)
{
   int i, j, c1, c2;

   /* I'm using an adjacenty matrix.  Set it so that all entries are zero. */

   Adj.resize(26);
   for (i = 0; i < Adj.size(); i++) Adj[i].resize(26, 0);

   /* Now go through the words, and set edges in the adjacency matrix.
      You should make sure that you don't set an edge from a node to itself. */

   for (i = 0; i < words.size(); i++) {
     for (j = 1; j < words[i].size(); j++) {
       c1 = words[i][j-1] - 'a';
       c2 = words[i][j] - 'a';
       if (c1 != c2) Adj[c1][c2] = 1;
     }
   }

   /* Print the adjacency matrix. */

   printf("  ");
   for (i = 'a'; i <= 'z'; i++) printf("%c", i);
   printf("\n");
   for (i = 0; i < Adj.size(); i++) {
     printf("%c ", 'a'+i);
     for (j = 0; j < Adj.size(); j++) printf("%d", Adj[i][j]);
     printf("\n");
   }
 
   /* Set all Visited fields to zero, and do a DFS on every node.
      If you discover a cycle, return "Impossible" */

   Visited.resize(Adj.size(), 0);
   for (i = 0; i < Adj.size(); i++) {
     if (DFS(i)) return "Impossible";
   }

   /* If you haven't found any cycles, return "Possible" */

   return "Possible";
}