- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: January, 2017 -
**Competitors who opened the problem**: 243 -
**Competitors who submitted a solution**: 139 -
**Number of correct solutions**: 73 -
**Accuracy (percentage correct vs those who opened)**: 30.0% -
**Average Correct Time**: 30 minutes, 47 seconds.

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:

- Zero means that the node has never been visited in the DFS.
- One means that the node is currently being visited by the DFS to determine if it is in a cycle.
- Two means that the node's DFS has completed, and it's not part of a cycle.

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.

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 00000000000000000000000000And here's the commented code (in

/* 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"; } |